The wobbly logic engine: proving hardness of non-rigid geometric graph representations
Fekete, Sandor P. and Houle, Michael and Whitesides, Sue
(1997)
The wobbly logic engine: proving hardness of non-rigid geometric graph representations.
Published In:
Graph drawing : 5th international symposium, GD '97, Rome, Italy, September 18 - 20, 1997 ; proceedings, Lecture notes in computer science. 1353 Springer 1997, pp. 272-283.
Abstract
In this paper we describe a general technique for establishing NP-hardness of graph representations. This technique is a generalization of the tool called the logic engine. We show that it is possible to extend it to a wobbly logic engine,which provides a proof method of NP-hardness for a variety of graph representations for which the set of feasible representations does not have to be discrete. This includes representations by visibility and intersection. In particular, we give a first proof that it is NP-hard to decide whether a graph has a nondegenerate z-axis parallel visibility representation (ZPR) by unit squares.
Download: |
Download (2MB) | Preview |
---|---|
Editorial actions: | ![]() |
ZAIK Number: | zpr97-273 |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 02 Apr 2001 00:00 |
Last Modified: | 19 Dec 2011 09:45 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/273 |