A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
Hristo N. Djidjev · SIAM Journal on Discrete Mathematics · 2006
We construct an optimal linear-time algorithm for the maximal planar subgraph problem: given a graph G, find a planar subgraph G' of G such that adding to G' an extra edge of G results in a nonplanar graph. Our solution is based on a fast data structure for incremental planarity testing of triconnected graphs and a dynamic graph search procedure. Our algorithm can be transformed into a new optimal planarity testing algorithm.