The Wobbly Logic Engine: Proving Hardness of Nonrigid Geometric Graph Representation ProblemsFekete, Sándor P. and Houle, Michael E. and Whitesides, Sue (1998) The Wobbly Logic Engine: Proving Hardness of Nonrigid Geometric Graph Representation Problems. In: Graph Drawing 5th International Symposium, GD '97, September 1820, 1997 , pp. 272283(Official URL: http://dx.doi.org/10.1007/3540639381_69). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540639381_69
AbstractThe logic engine technique has been used in the past to establish the NPhardness of a number of graph representations. The original technique can only be applied in those situations in which subgraphs exist for which the only possible layouts are rigid. In this paper we introduce an extension called the wobbly logic engine which can be used to prove the NPhardness of several graph representations for which no such rigid layouts exist, representations by visibility and intersection in particular. We illustrate the method by using the wobbly technique to show the NPhardness of deciding whether a graph has a nondegenerate zaxis parallel visibility representation (ZPR) by unit squares.
Actions (login required)
