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

Report ID: TR-309-91

---

Author: Cai, Jiazhen / Tarjan, Robert E. / Han, Xiafeng

---

Date: 1991-03-00

---

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.