The Wobbly Logic Engine: Proving Hardness of Non-rigid Geometric Graph Representation Problems

Fekete, Sándor P. and Houle, Michael E. and Whitesides, Sue (1998) The Wobbly Logic Engine: Proving Hardness of Non-rigid Geometric Graph Representation Problems. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 272-283 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_69).

Full text not available from this repository.

Abstract

The logic engine technique has been used in the past to establish the NP-hardness 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 NP-hardness 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 NP-hardness of deciding whether a graph has a nondegenerate z-axis parallel visibility representation (ZPR) by unit squares.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_69
Classifications:G Algorithms and Complexity > G.999 Others
P Styles > P.900 Visibility
G Algorithms and Complexity > G.560 Geometry
ID Code:91

Repository Staff Only: item control page

References

H. Alt , M. Godau, and S. Whitesides. Universal 3-dimensional visibility representations for graphs. Proc. Graph Drawing 95, Passau 1996. Lecture Notes in Computer Science Vol. 1027, Springer-Verlag, 1996, pp. 8-19.

A. Bachem, S.P. Fekete, B. Knab, R. Schrader, I. Vannahme, I. Weber, R. Wegener, K. Weinbrecht, and B. Wichern. Analyse großer Datenmengen und Clusteralgorithmen im Bausparwesen. In Geld, Finanzwirtschaft, Banken und Versicherungen. Editors C. Hipp et al., VVW Karlsruhe, 1997.

P. Bose, H. Everett, S.P. Fekete, A. Lubiw, H. Meijer, K. Romanik, T. Shermer, and S. Whitesides. On a visibility representation for graphs in three dimensions. Proc. Graph Drawing '93, Paris (Sèvres), 1993, pp. 38-39.

P. Bose, H. Everett, S.P. Fekete, A. Lubiw, H. Meijer, K. Romanik, T. Shermer, and S. Whitesides. On a visibility representation for graphs in three dimensions. Snapshots of Computational and Discrete Geometry, 3, eds. D. Avis and P. Bose, McGill University School of Computer Science Technical Report SOCS-94.50,July 1994, pp. 2-25.

P. Bose, H. Everett, S.P. Fekete, M.E. Houle, A. Lubiw, H. Meijer, K. Romanik, G. Rote, T. Shermer, and S. Whitesides. A visibility representation for graphs in three dimensions. Technical Report ZPR 97-253, Center for Parallel Computing, 1997. Available at ftp://ftp.zpr.uni-koeln.de/pub/papers/zpr97-253.ps.gz.

S. Bhatt and S. Cosmadakis. The complexity of minimizing wire lengths in VLSI layouts. Information Processing Letters, v. 25, 1987, pp. 263-267.

F.J. Brandenburg. Nice drawings of graphs and trees are computationally hard. Technical Report MIP-8820, Fakultät für Mathematik und Informatik, Univ. Passau, 1988.

F.J. Cobos, J.C. Dana, F. Hurtado, A. Marquez, and F. Mateos. On a visibility representation of graphs. Proc. Graph Drawing 95, Passau 1996. Lecture Notes in Computer Science Vol.1027, Springer-Verlag, 1996, pp. 152-161.

R. Cohen, P. Eades, T. Lin, and F. Ruskin. Three-dimensional graph drawing. Proc. Graph Drawing 94, Princeton NJ, 1994. Lecture Notes in Computer Science Vol. 894, Springer-Verlag, 1995, pp. 1-11.

L. Danzer, B. Grünbaum, and V. Klee. Helly's theorem and its relatives. Convexity, Proc. 7th ACM Symp. Pure Math., 1963, pp. 101-181.

A. Dean and J. Hutchinson. Rectangle visibility representations of bipartite graphs. Proc. Graph Drawing 94, Princeton NJ, 1994. Lecture Notes in Computer Science Vol. 894, Springer-Verlag, 1995, pp. 159-166.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for automatic graph drawing: an annotated bibliography. Comput. Geometry: Theory and Applications, 4, 1994, pp. 235-282. Also available from wilma.cs.brown.edu by ftp.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Graph Drawing. Algorithms for geometric representation of graphs. Prentice Hall, to appear.

G. Di Battista, G. Liotta and S. Whitesides. The strength of weak proximity. Proc. Graph Drawing 95, Passau 1996. Lecture Notes in Computer Science Vol. 1027, Springer-Verlag, 1996.

G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science, 61, 1988, pp. 175-198.

P. Eades and S. Whitesides. The realization problem for Euclidean minimum spaning trees is NP-hard. In Proc. 10th ACM Symp. on Computational Geometry, 1994, pp. 49-56.

P. Eades and S. Whitesides. The logic engine and the realization problem for nearest neighbor graphs. Theoretical Computer Science, 169(1), 1996, pp- 23-37.

H. ElGindy, G. Liotta, A. Lubiw, H. Meijer and S. Whitesides. Recognizing rectangle of influence drawable graphs. Proc. Graph Drawing 94, Princeton NJ, 1994. Lecture Notes in Computer Science LNCS #894, Springer-Verlag, 1995, pp. 352-363.

S.P. Fekete, M.E. Houle, and S. Whitesides. New results on a visibility representation of graphs in 3D. Proc. Graph Drawing 95, Passau 1996. Lecture Notes in Computer Science Vol. 1027, Springer-Verlag, 1996, pp. 234-241.

S.P. Fekete, M.E. Houle, and S. Whitesides. The wobbly logic engine: proving hardness of non-rigid graph representation problems. (Full version). Technical Report ZPR 97-273, Center for Parallel Computing, 1997. Available at ftp://ftp.zpr.uni-koeln.de/pub/papers/zpr97-273.ps.gz.

S.P. Fekete and H. Meijer. Rectangle and box visibility graphs in 3D. To appear in International Journal of Computational Geometry and Applications. Available at ftp://ftp.zpr.uni-koeln.de/pub/papers/zpr96-224.ps.gz.

M. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.

J. Hutchison, T. Shermer, and A. Vince. On representations of some thickness-two graphs. Proc. Graph Drawing 95, Passau 1996. Lecture Notes in Computer Science Vol. 1027, Springer-Verlag, 1996, pp. 324-332.

P.J. Idicula. Drawing trees in grids. Master's thesis, Departement of Computer Science, University Auckland, 1990.

K. Romanik. Directed VR-representable graphs have unbounded dimension. Proc. Graph Drawing '94, Princeton, NJ, 1994. Lecture Notes in Computer Science Vol. 894, Springer-Verlag, 1995, pp. 177-181.

R. Tamassia and I.G. Tollis. A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1, 1986, pp. 321-341.