graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a branch of

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a squaregraph is a type of

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

that can be drawn in the plane in such a way that every bounded

face The face is the front of the head that features the eyes, nose and mouth, and through which animals express many of their emotions. The face is crucial for human identity, and damage such as scarring or developmental deformities may affect th ...

is a

quadrilateral In Euclidean geometry, geometry a quadrilateral is a four-sided polygon, having four Edge (geometry), edges (sides) and four Vertex (geometry), corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''l ...

and every vertex with three or fewer neighbors is incident to an unbounded face.

Related graph classes

The squaregraphs include as special cases

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only p ...

grid graph In graph theory, a lattice graph, mesh graph, or grid graph is a Graph (discrete mathematics), graph whose graph drawing, drawing, Embedding, embedded in some Euclidean space , forms a regular tiling. This implies that the group (mathematics), g ...

s, gear graphs, and the graphs of

polyomino A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling. Polyominoes have been used in popu ...

s. As well as being

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

s, squaregraphs are

median graph In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertex (graph theory), vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest pat ...

s, 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.. See for a discussion of planar median graphs more generally. As with median graphs more generally, squaregraphs are also partial cubes: their vertices can be labeled with binary strings such that the

Hamming distance In information theory, the Hamming distance between two String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ...

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 In graph theory, a circle graph is the intersection graph of a Chord diagram (mathematics), chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of Chord (geometry), chords of a circle such tha ...

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:. *They are the

s that do not contain as an

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

any member of an infinite family of forbidden graphs. These forbidden graphs are the cube (the simplex graph of ''K''₃), the

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...

of an edge and a

claw A claw is a curved, pointed appendage found at the end of a toe or finger in most amniotes (mammals, reptiles, birds). Some invertebrates such as beetles and spiders have somewhat similar fine, hooked structures at the end of the leg or Arthro ...

''K''_1,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 In vascular plants, the roots are the plant organ, organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often bel ...

) 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 In mathematics, hyperbolic geometry (also called Lobachevskian geometry or Bolyai– Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For any given line ''R'' and point ''P' ...

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 as part of a

linear time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

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 In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

of squaregraphs, and for finding a vertex minimizing the maximum distance to all other vertices.

Notes

References

*. *. *. * *{{citation , last1 = Soltan , first1 = P. , last2 = Zambitskii , first2 = D. , last3 = Prisǎcaru , first3 = C. , language = Russian , location = Chişinǎu, Moldova , publisher = Ştiinţa , title = Extremal Problems on Graphs and Algorithms of their Solution , year = 1973. Graph families Planar graphs Bipartite graphs