Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Based on a recursive version of Hopcroft and Tarjan's planarity testing

algorithm, we develop anO(mlogn)-time algorithm to find a maximal

planar subgraph.

- This technical report has been published as
- An
O(mlogn)-Time Algorithm for the Maximal

Planar Subgraph Problem. Jiazhen Cai, Xiafeng Han

and Robert E. Tarjan,SIAM J. Comput.22(1993) 1142-1162.