Quick links

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

Report ID:
TR-309-91
Date:
February 1991
Pages:
26
Download Formats:
[PDF]

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.
Follow us: Facebook Twitter Linkedin