THE COMPLEXITY OF DETECTING CROSSING-FREE CONFIGURATIONS IN THE PLANE

被引：22

作者：

JANSEN, K

WOEGINGER, GJ

机构：

[1] UNIV TRIER,FACHBEREICH 4,W-5500 TRIER,GERMANY

[2] GRAZ TECH UNIV,INST INFORMAT ARBEITUNG,A-8010 GRAZ,AUSTRIA

来源：

BIT | 1993年 / 33卷 / 04期

关键词：

ALGORITHMIC COMPLEXITY; PLANAR LAYOUTS; GEOMETRY;

D O I：

10.1007/BF01990536

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The computational complexity of the following type of problem is studied. Given a geometric graph G = (P, S) where P is a set of points in the Euclidean plane and S a set of straight (closed) line segments between pairs of points in P, we want to know whether G possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.

引用

页码：580 / 595

页数：16

共 7 条

[1]

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

[2] NONCROSSING SUBGRAPHS IN TOPOLOGICAL LAYOUTS [J].