(Standard) Planarity

Definition

A graph is planar if it can be embedded in the plane such that no two edges cross.

Complexity

Planarity can be solved in linear time, see (Patrignani 2013) and the corresponding Wikipedia Article for a historic overview over the various solution. Haeupler and Tarjan (2008) and Brandes (2009) give very accessible descriptions of the state-of-the art planarity tests.

Related Problems

• Reduces to Level Planarity (Schaefer 2013)?
• Reduces to Partitioned 2-page Book Embedding (Schaefer 2013)?
• Trivially reduces to ec-Planarity by using an empty constraint set (Schaefer 2013).
• Trivially reduces to Partial Rotation Planarity by using an empty contraint set (Schaefer 2013).
• Reduces to Partial Planarity (Schaefer 2014)?

See also

• Planar Graphs: Theory and Algorithms (Nishizeki and Chiba 1988)
• Handbook on Graph Drawing and Visualization (Patrignani 2013)
• Wikipedia Article
• Information System on Graph Classes and their Inclusions Entry

References

Brandes, Ulrik. 2009. “The Left-Right Planarity Test.” https://www.uni-konstanz.de/algo/publications/b-lrpt-sub.pdf.

Haeupler, Bernhard, and Robert E. Tarjan. 2008. “Planarity Algorithms via PQ-Trees (Extended Abstract).” Electronic Notes in Discrete Mathematics 31: 143–49. https://doi.org/10.1016/j.endm.2008.06.029.

Nishizeki, T., and N. Chiba. 1988. Planar Graphs: Theory and Algorithms. North-Holland.

Patrignani, Maurizio. 2013. “Planarity Testing and Embedding.” In Handbook on Graph Drawing and Visualization, edited by Roberto Tamassia, 1–42. Chapman; Hall/CRC. https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/planarity.pdf.

Schaefer, Marcus. 2013. “Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants.” Journal of Graph Algorithms and Applications 17 (4): 367–440. https://doi.org/10.7155/jgaa.00298.

———. 2014. “Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph.” In Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, 13–24. Springer International Publishing. https://doi.org/10.1007/978-3-662-45803-7_2.