Squaregraph


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.

Related graph classes

The 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 that lies on shortest paths between each pair of the three vertices. 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 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.

Characterization

Squaregraphs may be characterized in several ways other than via their planar embeddings:
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 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.
Several algorithmic problems on squaregraphs may be computed more efficiently than in more general planar or median graphs; for instance, and present linear time algorithms for computing the diameter of squaregraphs, and for finding a vertex minimizing the maximum distance to all other vertices.