ON THE COMPLEXITY OF EMBEDDING PLANAR GRAPHS TO MINIMIZE CERTAIN DISTANCE MEASURES

被引：35

作者：

BIENSTOCK, D

MONMA, CL

机构：

[1] Bell Communications Research, Morristown, NJ 07960

来源：

ALGORITHMICA | 1990年 / 5卷 / 01期

关键词：

Embedding; Outer faces; Planar graphs;

D O I：

10.1007/BF01840379

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present polynomial-time algorithms for computing an embedding of a planar graph that minimizes the outerplanarity, or the width, or the radius, or some other measures of distance to the outer face. On the other hand, we show it is NP-hard to compute an embedding that minimizes the diameter of the dual graph. © 1990 Springer-Verlag New York Inc.

引用

页码：93 / 109

页数：17

共 10 条

[1]

Aggarwal A., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P186, DOI 10.1109/SFCS.1985.37

[2]

Baker B. S., 1983, 24th Annual Symposium on Foundations of Computer Science, P265, DOI 10.1109/SFCS.1983.7

[3] ON THE COMPLEXITY OF COVERING VERTICES BY FACES IN A PLANAR GRAPH [J].

BIENSTOCK, D ;

MONMA, CL .

SIAM JOURNAL ON COMPUTING, 1988, 17 (01) :53-76

[4]

BIENSTOCK D, IN PRESS NETWORKS

[5]

DOLEV D, 1984, ADV COMPUTING RES, V2, P147

[6]

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

[7]

Lovasz L., 1979, COMBINATORIAL PROBLE

[8] GRAPH MINORS .3. PLANAR TREE-WIDTH [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1984, 36 (01) :49-64

[9]

TARJAN RE, 1973, SIAM J COMPUT, P135

[10]

Welsh D.J.A., 1976, MATROID THEORY

← 1 →