Classification and detection of obstructions to planarity
Almira Karabeg · Linear and Multilinear Algebra · 1990
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.