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

, the left-right planarity test or de Fraysseix–Rosenstiehl planarity criterion is a characterization of

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 based on the properties of the depth-first search trees, published by and used by them with

Patrice Ossona de Mendez Patrice Ossona de Mendez is a French mathematician specializing in topological graph theory who works as a researcher at the Centre national de la recherche scientifique in Paris.. He is editor-in-chief of the ''European Journal of Combinatorics' ...

to develop 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 ...

planarity testing In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer scie ...

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

. In a 2003 experimental comparison of six planarity testing algorithms, this was one of the fastest algorithms tested..

T-alike and T-opposite edges

For any

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible al ...

of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

''G'', the edges encountered when discovering a vertex for the first time define a depth-first search tree ''T'' of ''G''. This is a

Trémaux tree In graph theory, a Trémaux tree of an undirected graph G is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of G connects an ancestor–descendant pair in the tree. Trémaux trees ar ...

, meaning that the remaining edges (the cotree) each connect a pair of vertices that are related to each other as an ancestor and descendant in ''T''. Three types of patterns can be used to define two relations between pairs of cotree edges, named the ''T''-alike and ''T''-opposite relations. In the following figures, simple circle nodes represent vertices, double circle nodes represent subtrees, twisted segments represent tree paths, and curved arcs represent cotree edges. The root of each tree is shown at the bottom of the figure. In the first figure, the edges labeled

\alpha

and

\beta

are ''T''-alike, meaning that, at the endpoints nearest the root of the tree, they will both be on the same side of the tree in every planar drawing. In the next two figures, the edges with the same labels are ''T''-opposite, meaning that they will be on different sides of the tree in every planar drawing.

The characterization

Let ''G'' be a graph and let ''T'' be a Trémaux tree of ''G''. The graph ''G'' is planar if and only if there exists a partition of the cotree edges of ''G'' into two classes so that any two edges belong to the same class if they are ''T''-alike and any two edges belong to different classes if they are ''T''-opposite. This characterization immediately leads to an (inefficient) planarity test: determine for all pairs of edges whether they are ''T''-alike or ''T''-opposite, form an auxiliary graph that has a vertex for each connected component of ''T''-alike edges and an edge for each pair of ''T''-opposite edges, and check whether this auxiliary graph is bipartite. Making this algorithm efficient involves finding a subset of the ''T''-alike and ''T''-opposite pairs that is sufficient to carry out this method without determining the relation between all edge pairs in the input graph.

T-alike and T-opposite edges

The characterization

References

Further reading