An O(n²) maximal planarization algorithm based on PQ-trees

Abstract

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.