An <i>O</i>(<i>m</i> log <i>n</i>)-Time Algorithm for the Maximal Planar Subgraph Problem

Abstract:

Based on a recursive version of Hopcroft and Tarjan's planarity testing
algorithm, we develop an O(m log n)-time algorithm to find a maximal
planar subgraph.

This technical report has been published as

An O(m log n)-Time Algorithm for the Maximal
Planar Subgraph Problem. Jiazhen Cai, Xiafeng Han
and Robert E. Tarjan, SIAM J. Comput.
22 (1993) 1142-1162.