# 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: |
Postscript
- Preprinted Version
Download (2MB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

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 |