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

被引：31

作者：

CAI, JZ

HAN, XF

TARJAN, RE

机构：

[1] PRINCETON UNIV, DEPT COMP SCI, PRINCETON, NJ 08544 USA

[2] NEC RES INST, PRINCETON, NJ 08540 USA

来源：

SIAM JOURNAL ON COMPUTING | 1993年 / 22卷 / 06期

关键词：

ALGORITHM; COMPLEXITY; DEPTH-FIRST-SEARCH; EMBEDDING; PLANAR GRAPH; SELECTION TREE;

D O I：

10.1137/0222068

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：1142 / 1162

页数：21

共 15 条

[1] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].

BOOTH, KS ;

LUEKER, GS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379

[2] A LINEAR ALGORITHM FOR EMBEDDING PLANAR GRAPHS USING PQ-TREES [J].

CHIBA, N ;

NISHIZEKI, T ;

ABE, S ;

OZAWA, T .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (01) :54-76

[3] INCREMENTAL PLANARITY TESTING [J].

DIBATTISTA, G ;

TAMASSIA, R .

30TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 1989, :436-441

[4]

Even S., 1976, Theoretical Computer Science, V2, P339, DOI 10.1016/0304-3975(76)90086-4

[5]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[6]

HALL DW, 1955, ELEMENTARY TOPOLOGY

[7] EFFICIENT PLANARITY TESTING [J].

HOPCROFT, J ;

TARJAN, R .

JOURNAL OF THE ACM, 1974, 21 (04) :549-568

[8]

Horowitz E., 1983, FUNDAMENTALS DATA ST

[9] O (NORMAL-2) ALGORITHMS FOR GRAPH PLANARIZATION [J].

JAYAKUMAR, R ;

THULASIRAMAN, K ;

SWAMY, MNS .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1989, 8 (03) :257-267

[10]

KOBAYASHI N, 1991, IEICE TRANS COMMUN, V74, P657

← 1 2 →