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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (2MB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
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