Title: An O(n2) 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.
Publication Year: 1992
Publication Date: 1992-01-01
Language: en
Type: book
Access and Citation
Cited By Count: 33
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot