Combinatorics and geometry of finite and infinite squaregraphs

Abstract

Squaregraphs were originally defined as finite plane graphs in which all inner faces are quadrilaterals (i.e., 4-cycles) and all inner vertices (i.e., the vertices not incident with the outer face) have degrees larger than three. The planar dual of a finite squaregraph is determined by a triangle-free chord diagram of the unit disk, which could alternatively be viewed as a triangle-free line arrangement in the hyperbolic plane. This representation carries over to infinite plane graphs with finite vertex degrees in which the balls are finite squaregraphs. Algebraically, finite squaregraphs are median graphs for which the duals are finite circular split systems. Hence squaregraphs are at the crosspoint of two dualities, an algebraic and a geometric one, and thus lend themselves to several combinatorial interpretations and structural characterizations. With these and the 5-colorability theorem for circle graphs at hand, we prove that every squaregraph can be isometrically embedded into the Cartesian product of five trees. This embedding result can also be extended to the infinite case without reference to an embedding in the plane and without any cardinality restriction when formulated for median graphs free of cubes and further finite obstructions. Further, we exhibit a class of squaregraphs that can be embedded into the product of three trees and we characterize those squaregraphs that are embeddable into the product of just two trees. Finally, finite squaregraphs enjoy a number of algorithmic features that do not extend to arbitrary median graphs. For instance, we show that median-generating sets of finite squaregraphs can be computed in polynomial time, whereas, not unexpectedly, the corresponding problem for median graphs turns out to be NP-hard.

46 pages, 14 figures

References in corpus (5)

• The lattice dimension of a graph
• Coarse decompositions of boundaries for CAT(0) groups
• Manhattan orbifolds
• Kazhdan and Haagerup properties from the median viewpoint
• Optimal Angular Resolution for Face-Symmetric Drawings

Cited by in corpus (12)

• Superpatterns and Universal Point Sets
• Track Layouts, Layered Path Decompositions, and Leveled Planarity
• On embeddings of CAT(0) cube complexes into products of trees
• Manhattan orbifolds
• Shortest path problem in rectangular complexes of global nonpositive curvature
• Optimally fast incremental Manhattan plane embedding and planar tight span construction
• Helly groups
• Isometric embeddings in trees and their use in the diameter problem
• Ramified rectilinear polygons: coordinatization by dendrons
• Cubic Planar Graphs that cannot be Drawn on few Lines
• Diameter, radius and all eccentricities in linear time for constant-dimension median graphs
• Graph-Theoretic Solutions to Computational Geometry Problems