Classification and detection of obstructions to planarity

Abstract

We use the PQ-tree data structure and the Lempel. Even and Cederbaum planarity testing algorithm to investigate obstructions to planarity for a given nonplaner graph G=(V,E), |V|=n.. We classify obstructions to planarity as they appear in this algorithm and give and O(n) algorithm for locating them.

Related Papers

• → On the planarity of infinite 2-complexes(1997)2 cited
• → Classification and detection of obstructions to planarity(1990)11 cited
• → Simultaneous FPQ-Ordering and Hybrid Planarity Testing(2020)