An O(n2) maximal planarization algorithm based on PQ-trees
Goos Kant · Utrecht University Repository (Utrecht University) · 1992
In this paper we investigate the problem how to delete a number of edges from a nonplanar graph G such that the resulting graph G’ is maximal planar, i.e., such that we cannot add an edge e E G – G’ to G’ without destroying planarity. Actually, our algorithm is a corrected and more generalized version of the maximal planarization algorithm of Jayakumar et al., based on the planarity testing algorithm using PQ-trees of Booth & Lucker. Our algorithm can be implemented to run in O(n²) time.