O(m log n)-time algorithm for the maximal planar subgraph problem

Jiazhen Cai, Xiaofeng Han, Robert E. Tarjan

Research output: Contribution to journalArticle

42 Scopus citations

Abstract

Based on a new version of the Hopcroft and Tarjan planarity testing algorithm, this paper develops an O(m log n)-time algorithm to find a maximal planar subgraph.

Original languageEnglish (US)
Pages (from-to)1142-1162
Number of pages21
JournalSIAM Journal on Computing
Volume22
Issue number6
DOIs
StatePublished - Jan 1 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'O(m log n)-time algorithm for the maximal planar subgraph problem'. Together they form a unique fingerprint.

  • Cite this