As well as being planar graphs, squaregraphs are median graphs, meaning that for every three vertices u, v, and w there is a unique median vertex m(u,v,w) that lies on shortest paths between each pair of the three vertices.[1] As with median graphs more generally, squaregraphs are also partial cubes: their vertices can be labeled with binary strings such that the Hamming distance between strings is equal to the shortest path distance between vertices.
The graph obtained from a squaregraph by making a vertex for each zone (an equivalence class of parallel edges of quadrilaterals) and an edge for each two zones that meet in a quadrilateral is a circle graph determined by a triangle-freechord diagram of the unit disk.[2]
Characterizationedit
Squaregraphs may be characterized in several ways other than via their planar embeddings:[2]
They are the median graphs that do not contain as an induced subgraph any member of an infinite family of forbidden graphs. These forbidden graphs are the cube (the simplex graph of K3), the Cartesian product of an edge and a clawK1,3 (the simplex graph of a claw), and the graphs formed from a gear graph by adding one more vertex connected to the hub of the wheel (the simplex graph of the disjoint union of a cycle with an isolated vertex).
They are the graphs that are connected and bipartite, such that (if an arbitrary vertex r is picked as a root) every vertex has at most two neighbors closer to r, and such that at every vertex v, the link of v (a graph with a vertex for each edge incident to v and an edge for each 4-cycle containing v) is either a cycle of length greater than three or a disjoint union of paths.
The characterization of squaregraphs in terms of distance from a root and links of vertices can be used together with breadth first search as part of a linear timealgorithm for testing whether a given graph is a squaregraph, without any need to use the more complex linear-time algorithms for planarity testing of arbitrary graphs.[2]
Several algorithmic problems on squaregraphs may be computed more efficiently than in more general planar or median graphs; for instance, Chepoi, Dragan & Vaxès (2002) and Chepoi, Fanciullini & Vaxès (2004) present linear time algorithms for computing the diameter of squaregraphs, and for finding a vertex minimizing the maximum distance to all other vertices.
Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002), "Center and diameter problem in planar quadrangulations and triangulations", Proc. 13th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA 2002), pp. 346–355.
Chepoi, Victor; Fanciullini, Clémentine; Vaxès, Yann (2004), "Median problem in some plane triangulations and quadrangulations", Computational Geometry, 27 (3): 193–210, doi:10.1016/j.comgeo.2003.11.002.
Peterin, Iztok (2006), "A characterization of planar median graphs", Discussiones Mathematicae Graph Theory, 26 (1): 41–48, doi:10.7151/dmgt.1299
Soltan, P.; Zambitskii, D.; Prisǎcaru, C. (1973), Extremal Problems on Graphs and Algorithms of their Solution (in Russian), Chişinǎu, Moldova: Ştiinţa.
October 26, 2023
squaregraph, graph, theory, branch, mathematics, squaregraph, type, undirected, graph, that, drawn, plane, such, that, every, bounded, face, quadrilateral, every, vertex, with, three, fewer, neighbors, incident, unbounded, face, squaregraph, contents, related,. In graph theory a branch of mathematics a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbounded face A squaregraph Contents 1 Related graph classes 2 Characterization 3 Algorithms 4 Notes 5 ReferencesRelated graph classes editThe squaregraphs include as special cases trees grid graphs gear graphs and the graphs of polyominos As well as being planar graphs squaregraphs are median graphs meaning that for every three vertices u v and w there is a unique median vertex m u v w that lies on shortest paths between each pair of the three vertices 1 As with median graphs more generally squaregraphs are also partial cubes their vertices can be labeled with binary strings such that the Hamming distance between strings is equal to the shortest path distance between vertices The graph obtained from a squaregraph by making a vertex for each zone an equivalence class of parallel edges of quadrilaterals and an edge for each two zones that meet in a quadrilateral is a circle graph determined by a triangle free chord diagram of the unit disk 2 Characterization editSquaregraphs may be characterized in several ways other than via their planar embeddings 2 They are the median graphs that do not contain as an induced subgraph any member of an infinite family of forbidden graphs These forbidden graphs are the cube the simplex graph of K3 the Cartesian product of an edge and a claw K1 3 the simplex graph of a claw and the graphs formed from a gear graph by adding one more vertex connected to the hub of the wheel the simplex graph of the disjoint union of a cycle with an isolated vertex They are the graphs that are connected and bipartite such that if an arbitrary vertex r is picked as a root every vertex has at most two neighbors closer to r and such that at every vertex v the link of v a graph with a vertex for each edge incident to v and an edge for each 4 cycle containing v is either a cycle of length greater than three or a disjoint union of paths They are the dual graphs of arrangements of lines in the hyperbolic plane that do not have three mutually crossing lines Algorithms editThe characterization of squaregraphs in terms of distance from a root and links of vertices can be used together with breadth first search as part of a linear time algorithm for testing whether a given graph is a squaregraph without any need to use the more complex linear time algorithms for planarity testing of arbitrary graphs 2 Several algorithmic problems on squaregraphs may be computed more efficiently than in more general planar or median graphs for instance Chepoi Dragan amp Vaxes 2002 and Chepoi Fanciullini amp Vaxes 2004 present linear time algorithms for computing the diameter of squaregraphs and for finding a vertex minimizing the maximum distance to all other vertices Notes edit Soltan Zambitskii amp Prisǎcaru 1973 See Peterin 2006 for a discussion of planar median graphs more generally a b c Bandelt Chepoi amp Eppstein 2010 References editBandelt Hans Jurgen Chepoi Victor Eppstein David 2010 Combinatorics and geometry of finite and infinite squaregraphs SIAM Journal on Discrete Mathematics 24 4 1399 1440 arXiv 0905 4537 doi 10 1137 090760301 S2CID 10788524 Chepoi Victor Dragan Feodor Vaxes Yann 2002 Center and diameter problem in planar quadrangulations and triangulations Proc 13th Annu ACM SIAM Symp on Discrete Algorithms SODA 2002 pp 346 355 Chepoi Victor Fanciullini Clementine Vaxes Yann 2004 Median problem in some plane triangulations and quadrangulations Computational Geometry 27 3 193 210 doi 10 1016 j comgeo 2003 11 002 Peterin Iztok 2006 A characterization of planar median graphs Discussiones Mathematicae Graph Theory 26 1 41 48 doi 10 7151 dmgt 1299 Soltan P Zambitskii D Prisǎcaru C 1973 Extremal Problems on Graphs and Algorithms of their Solution in Russian Chisinǎu Moldova Stiinţa Retrieved from https en wikipedia org w index php title Squaregraph amp oldid 1094649019, wikipedia, wiki, book, books, library,
