Fixed edge-length graph drawing is NP-hard. (English) Zbl 0744.05053
Summary: The problem of drawing a graph with prescribed edge lengths such that edges do not cross is proved NP-hard, even in the case where all edge lengths are one and the graph is 2-connected. The proof is an interesting interplay of geometry and combinatorics. First we use geometrical methods to transform a rather synthetic “Orientation Problem” to our graph drawing problem; then we use combinatorial methods to transform a well- known “Flow Problem” to the orientation problem.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 94C15 | Applications of graph theory to circuits and networks |
References:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), MacMillan: MacMillan London · Zbl 1134.05001 |
| [2] | Booth, K.; Lueker, G., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13, 335-379 (1976) · Zbl 0367.68034 |
| [3] | Chiba, N.; Nishizeki, T.; Abe, S.; Ozawa, T., A linear algorithm for embedding planar graphs using PQ-trees, J. Comput. System Sci., 30, 1, 54-76 (1985) · Zbl 0605.68060 |
| [4] | Eades, P.; Tamassia, R., Algorithms for automatic graph drawing: An annotated bibliography, (Tech. Rept. 82 (1987), Department of Computer Science, University of Queensland) · Zbl 0804.68001 |
| [5] | Garey, M. R.; Johnson, D. S., Computers and Intractability, (A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA) · Zbl 0369.90053 |
| [6] | Hopcroft, J.; Tarjan, R., Efficient planarity testing, J. ACM, 21, 4, 549-568 (1974) · Zbl 0307.68025 |
| [7] | Johnson, D. S., The NP-completeness column: An ongoing guide, J. Algorithms, 3, 89-99 (1982) · Zbl 0494.68048 |
| [8] | Johnson, D. S., The NP-completeness column: An ongoing guide, J. Algorithms, 5, 147-160 (1984) · Zbl 0545.68032 |
| [9] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060 |
| [10] | Reingold, E. M.; Nievergelt, J.; Deo, N., Combinatorial Algorithms, (Theory and Practice (1977), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) · Zbl 0478.68058 |
| [11] | Saxe, J. B., Two papers on graph embedding problems, (Tech. Rept. CMU-CS-80-102 (1980), Department of Computer Science, Carnegie-Mellon University: Department of Computer Science, Carnegie-Mellon University Pittsburgh, PA) |
| [12] | Supowit, K.; Reingold, E., The complexity of drawing trees nicely, Acta Inform., 18, 377-392 (1983) · Zbl 0493.68038 |
| [13] | Thomassen, C., Plane representations of graphs, (Bondy, J. A.; Murty, U. S.R., Progress in Graph Theory (1984), Academic Press: Academic Press New York), 43-70 · Zbl 0554.05021 |
| [14] | Tutte, W., A class of Abelian groups, Canad. J. Math., 8, 13-28 (1956) · Zbl 0070.02302 |
| [15] | Valiant, L. G., Universality considerations in VLSI circuits, IEEE Trans. Comput., 30, 131-140 (1981) · Zbl 0455.94046 |
| [16] | S. Whitesides, Private communication (1986).; S. Whitesides, Private communication (1986). |
| [17] | Younger, D. H., Integer flows, J. Graph Theory, 7, 349-357 (1983) · Zbl 0515.05057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
