Left-right planarity test

In graph theory, a branch of mathematics, the left-right planarity test or de Fraysseix–Rosenstiehl planarity criterion^[1] is a characterization of planar graphs based on the properties of the depth-first search trees, published by de Fraysseix and Rosenstiehl (1982, 1985)^[2][3] and used by them with Patrice Ossona de Mendez to develop a linear time planarity testing algorithm.^[4][5] In a 2003 experimental comparison of six planarity testing algorithms, this was one of the fastest algorithms tested.^[6]

T-alike and T-opposite edges

For any depth-first search of a graph 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, 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.

$\alpha$ and $\beta$ are T-alike

$\alpha$ and $\beta$ are T-opposite

$\alpha$ and $\beta$ are T-opposite

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

References

1. Auer, Christopher; Gleißner, Andreas; Hanauer, Kathrin; Vetter, Sebastian (2013), "Testing planarity by switching trains", Graph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers, Lecture Notes in Computer Science 7704, Berlin: Springer, pp. 557–558, doi:10.1007/978-3-642-36763-2_51.
2. de Fraysseix, H.; Rosenstiehl, P. (1982), "A depth-first-search characterization of planarity", Graph Theory (Cambridge, 1981), Annals of Discrete Mathematics 13, North-Holland, Amsterdam-New York, pp. 75–80, MR 671906.
3. de Fraysseix, H.; Rosenstiehl, P. (1985), "A characterization of planar graphs by Trémaux orders", Combinatorica 5 (2): 127–135, doi:10.1007/BF02579375, MR 815578.
4. de Fraysseix, Hubert; de Mendez, Patrice Ossona; Rosenstiehl, Pierre (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science 17 (5): 1017–1029, arXiv:math.CO/0610935, doi:10.1142/S0129054106004248, MR 2270949.
5. de Fraysseix, Hubert; Ossona de Mendez, Patrice (2012), "Trémaux trees and planarity", European Journal of Combinatorics 33 (3): 279–293, doi:10.1016/j.ejc.2011.09.012, MR 2864415.
6. Boyer, John M.; Cortese, Pier Francesco; Patrignani, Maurizio; Di Battista, Giuseppe (2004), "Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers, Lecture Notes in Computer Science 2912, Berlin: Springer, pp. 25–36, doi:10.1007/978-3-540-24595-7_3, MR 2177580.

Additional reading

• Kaiser, Daniel (2009), Implementation und Animation des Links-Rechts-Planaritätstests (PDF), Bachelorarbeit (in German), University of Konstanz, FB Informatik und Informationswissenschaft