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

Jiazhen Cai; Xiaofeng Han; Robert E. Tarjan

doi:10.1137/0222068

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

Jiazhen Cai, Xiaofeng Han, Robert E. Tarjan

Research output: Contribution to journal › Article › peer-review

44 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 language	English (US)
Pages (from-to)	1142-1162
Number of pages	21
Journal	SIAM Journal on Computing
Volume	22
Issue number	6
DOIs	https://doi.org/10.1137/0222068
State	Published - 1993
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0222068

Cite this

@article{5a9b9dd62c3c4872b1439bdf178c9f58,

title = "O(m log n)-time algorithm for the maximal planar subgraph problem",

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.",

author = "Jiazhen Cai and Xiaofeng Han and Tarjan, {Robert E.}",

year = "1993",

doi = "10.1137/0222068",

language = "English (US)",

volume = "22",

pages = "1142--1162",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "6",

}

TY - JOUR

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

AU - Cai, Jiazhen

AU - Han, Xiaofeng

AU - Tarjan, Robert E.

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027829965&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027829965&partnerID=8YFLogxK

U2 - 10.1137/0222068

DO - 10.1137/0222068

M3 - Article

AN - SCOPUS:0027829965

SN - 0097-5397

VL - 22

SP - 1142

EP - 1162

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this