FIXED EDGE-LENGTH GRAPH DRAWING IS NP-HARD

被引：30

作者：

EADES, P ^{[1
]}

WORMALD, NC ^{[1
]}

机构：

[1] UNIV AUCKLAND, DEPT MATH, AUCKLAND, NEW ZEALAND

来源：

DISCRETE APPLIED MATHEMATICS | 1990年 / 28卷 / 02期

关键词：

2-connected graph; Computational geometry; graph layout; planar graph;

D O I：

10.1016/0166-218X(90)90110-X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The problem of drawing a graph with prescribed edge lengths such that edges do not cross is proved NP-hard, even in the case where all edge lengths are one and the graph is 2-connected. The proof is an interesting interplay of geometry and combinatorics. First we use geometrical methods to transform a rather synthetic "Orientation Problem" to our graph drawing problem; then we use combinatorial methods to transform a well-known "Flow Problem" to the orientation problem. © 1990.

引用

页码：111 / 134

页数：24

共 17 条

[1]

BONDY JA, 1976, GRAPH THEORY APPLICA

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