# Squaregraph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Squaregraph
> Markdown URL: https://mediated.wiki/source/Squaregraph.md
> Source: https://en.wikipedia.org/wiki/Squaregraph
> Source revision: 1094649019
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Planar graph with quadrilateral faces

A squaregraph.

In [graph theory](/source/Graph_theory), a branch of [mathematics](/source/Mathematics), a **squaregraph** is a type of [undirected graph](/source/Undirected_graph) that can be [drawn in the plane](/source/Graph_drawing) in such a way that every bounded [face](/source/Face_(geometry)) is a [quadrilateral](/source/Quadrilateral) and every [vertex](/source/Vertex_(graph_theory)) with three or fewer neighbors is incident to an unbounded face.

## Related graph classes

The squaregraphs include as special cases [trees](/source/Tree_(graph_theory)), [grid graphs](/source/Grid_graph), [gear graphs](/source/Gear_graph), and the graphs of [polyominos](/source/Polyomino).

As well as being [planar graphs](/source/Planar_graph), squaregraphs are [median graphs](/source/Median_graph), 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](/source/Partial_cube): their vertices can be labeled with [binary strings](/source/Bitvector) such that the [Hamming distance](/source/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](/source/Circle_graph) determined by a [triangle-free](/source/Triangle-free_graph) [chord diagram](/source/Chord_diagram_(mathematics)) of the unit disk.[2]

## Characterization

Squaregraphs may be characterized in several ways other than via their planar embeddings:[2]

- They are the [median graphs](/source/Median_graph) that do not contain as an [induced subgraph](/source/Induced_subgraph) any member of an infinite family of [forbidden graphs](/source/Forbidden_graph_characterization). These forbidden graphs are the cube (the [simplex graph](/source/Simplex_graph) of *K*3), the [Cartesian product](/source/Cartesian_product_of_graphs) of an edge and a [claw](/source/Claw_(graph_theory)) *K*1,3 (the simplex graph of a claw), and the graphs formed from a [gear graph](/source/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](/source/Bipartite_graph), such that (if an arbitrary vertex *r* is picked as a [root](/source/Rooted_graph)) 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](/source/Planar_dual) of [arrangements of lines](/source/Arrangement_of_lines) in the [hyperbolic plane](/source/Hyperbolic_space) that do not have three mutually-crossing lines.

## Algorithms

The characterization of squaregraphs in terms of distance from a root and links of vertices can be used together with [breadth first search](/source/Breadth_first_search) as part of a [linear time](/source/Linear_time) [algorithm](/source/Algorithm) for testing whether a given graph is a squaregraph, without any need to use the more complex linear-time algorithms for [planarity testing](/source/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)](#CITEREFChepoiDraganVaxès2002) and [Chepoi, Fanciullini & Vaxès (2004)](#CITEREFChepoiFanciulliniVaxès2004) present linear time algorithms for computing the [diameter](/source/Diameter) of squaregraphs, and for finding a vertex minimizing the maximum distance to all other vertices.

## Notes

1. **[^](#cite_ref-1)** [Soltan, Zambitskii & Prisǎcaru (1973)](#CITEREFSoltanZambitskiiPrisǎcaru1973). See [Peterin (2006)](#CITEREFPeterin2006) for a discussion of planar median graphs more generally.

1. ^ [***a***](#cite_ref-bce_2-0) [***b***](#cite_ref-bce_2-1) [***c***](#cite_ref-bce_2-2) [Bandelt, Chepoi & Eppstein (2010)](#CITEREFBandeltChepoiEppstein2010).

## References

- Bandelt, Hans-Jürgen; Chepoi, Victor; [Eppstein, David](/source/David_Eppstein) (2010), "Combinatorics and geometry of finite and infinite squaregraphs", *[SIAM Journal on Discrete Mathematics](/source/SIAM_Journal_on_Discrete_Mathematics)*, **24** (4): 1399–1440, [arXiv](/source/ArXiv_(identifier)):[0905.4537](https://arxiv.org/abs/0905.4537), [doi](/source/Doi_(identifier)):[10.1137/090760301](https://doi.org/10.1137%2F090760301), [S2CID](/source/S2CID_(identifier)) [10788524](https://api.semanticscholar.org/CorpusID:10788524).

- 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](/source/Computational_Geometry_(journal))*, **27** (3): 193–210, [doi](/source/Doi_(identifier)):[10.1016/j.comgeo.2003.11.002](https://doi.org/10.1016%2Fj.comgeo.2003.11.002).

- Peterin, Iztok (2006), ["A characterization of planar median graphs"](https://dk.um.si/Dokument.php?id=110389&dn=), *Discussiones Mathematicae Graph Theory*, **26** (1): 41–48, [doi](/source/Doi_(identifier)):[10.7151/dmgt.1299](https://doi.org/10.7151%2Fdmgt.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.

---
Adapted from the Wikipedia article [Squaregraph](https://en.wikipedia.org/wiki/Squaregraph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Squaregraph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.