Characterization
Squaregraphs may be characterized in several ways other than via their planar embeddings:
- 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.
Read more about this topic: Squaregraph