graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a branch of mathematics, a squaregraph is a type of

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

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

face The face is the front of an animal's 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 aff ...

is a

quadrilateral In geometry a quadrilateral is a four-sided polygon, having four edges (sides) and four corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''latus'', meaning "side". It is also called a tetragon, ...

and every

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

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, including only woody plants with secondary growth, plants that are ...

grid graph In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lat ...

gear graph This partial list of graphs contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own. For collected definitions of graph theory terms that do not refer to individual ...

s, 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 po ...

s. As well as being

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

s, squaregraphs are

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

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 cube In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cub ...

s: their vertices can be labeled with binary strings such that the

Hamming distance In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...

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. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if th ...

determined by a

triangle-free In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...

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 the mathematical field of 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. Definit ...

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 ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ ...

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 tars ...

''K''_1,3 (the simplex graph of a claw), and the graphs formed from a

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 Bipartite may refer to: * 2 (number) * Bipartite (theology), a philosophical term describing the human duality of body and soul * Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...

, such that (if an arbitrary vertex ''r'' is picked as a

root In vascular plants, the roots are the 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 below the sur ...

) 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 music, an arrangement is a musical adaptation of an existing composition. Differences from the original composition may include reharmonization, melodic paraphrasing, orchestration, or formal development. Arranging differs from orchestra ...

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 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 performed by t ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

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 center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...

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