AN O(M LOG N)-TIME ALGORITHM FOR THE MAXIMAL PLANAR SUBGRAPH PROBLEM

Authors
CAI JZ HAN XF TARJAN RE
Citation
Jz. Cai et al., AN O(M LOG N)-TIME ALGORITHM FOR THE MAXIMAL PLANAR SUBGRAPH PROBLEM, SIAM journal on computing, 22(6), 1993, pp. 1142-1162
Citations number
15
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
22
Issue
6
Year of publication
1993
Pages
1142 - 1162
Database
ISI
SICI code
0097-5397(1993)22:6<1142:AOLNAF>2.0.ZU;2-5
Abstract
Based on a new version of the Hopcroft and Tarjan planarity testing al gorithm, this paper develops an O(m log n)-time algorithm to find a ma ximal planar subgraph.