Technical Reports

Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:
TR-309-91
An O(m log n)-Time Algorithm for the Maximal Planar Subgraph Problem
Authors: Cai, Jiazhen, Han, Xiafeng, Tarjan, Robert E.
Date:March 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.