Abstract
We consider three closely related optimization problems, arising from the graph drawing and the VLSI research areas, and conjectured to be NP-hard, and we prove that, in fact, they are NP-complete. Starting from an orthogonal representation of a graph, i.e., a description of the shape of the edges that does not specify segment lengths or vertex positions, the three problems consist of providing an orthogonal grid drawing of it, while minimizing the area, the total edge length, or the maximum edge length, respectively.
Research supported in part by the CNR Project “Geometria Computazionale Robusta con Applicazioni alla Grafica ed al CAD”, and by the ESPRIT LTR Project 20244 (ALCOM-IT)
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. In F. Dehne, A. Rau-Chaplin, J.-R. Sack, and R. Tamassia, editors, Proc. 5th Workshop Algorithms Data Struct., volume 1272 of LNCS, pages 331–344. Springer-Verlag, 1997.
S. Bridgeman, G. Di Battista, W. Didimo, G. Liotta, R. Tamassia, and L. Vismara. Optimal compaction of orthogonal representations. In CGC Workshop on Geometric Computing, 1998.
G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.
D. Dolev and H. Trickey. On linear area embedding of planar graphs. Report cs-81-876, Stanford Univ., 1981.
U. Föβmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD’ 95), volume 1027 of LNCS, pages 254–266. Springer-Verlag, 1996.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979.
F. Harary. Graph Theory. Addison-Wesley, Reading, MA, 1972.
F. Hoffmann and K. Kriegel. Embedding rectilinear graphs in linear time. Inform. Process. Lett., 29:75–79, 1988.
G. W. Klau and P. Mutzel. Quasi-orthogonal drawing of planar graphs. Technical Report MPI-I 98-1-013, Max Planck Institut für Informatik, Saarbrücken, Germany, 1998.
G. W. Klau and P. Mutzel. Optimal compaction of orthogonal grid drawings. In G. Cornuejols, R. E. Burkard, and G. J. Woeginger, editors, Integer Progr. Comb. Opt. (Proc. IPCO’ 99), volume 1610 of LNCS, Springer-Verlag, to appear.
T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley-Teubner, 1990.
C. H. Papadimitriou. Computational Complexity. Addison-Wesley, Reading, MA, 1994.
M. Patrignani. On the complexity of orthogonal compaction. Technical Report RT-DIA-39-99, Dipartimento di Informatica e Automazione, Universit.a di Roma Tre, Rome, Italy, Jan. 1999.
R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421–444, 1987.
G. Vijayan and A. Wigderson. Rectilinear graphs and their embeddings. SIAM J. Comput., 14:355–372, 1985.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Patrignani, M. (1999). On the Complexity of Orthogonal Compaction. In: Dehne, F., Sack, JR., Gupta, A., Tamassia, R. (eds) Algorithms and Data Structures. WADS 1999. Lecture Notes in Computer Science, vol 1663. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48447-7_7
Download citation
DOI: https://doi.org/10.1007/3-540-48447-7_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66279-2
Online ISBN: 978-3-540-48447-9
eBook Packages: Springer Book Archive