Embedding a Graph in the Grid of a Surface with the Minimum Number of Bends Is NP-hard

Garrido, M. Ángeles and Márquez, Alberto (1998) Embedding a Graph in the Grid of a Surface with the Minimum Number of Bends Is NP-hard. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 124-133 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_56).

Full text not available from this repository.


This paper is devoted to the study of graph embeddings in the grid of non-planar surfaces. We provide an adequate model for those embeddings and we study the complexity of minimizing the number of bends. In particular, we prove that testing whether a graph admits a rectilinear (without bends) embedding essentially equivalent to a given embedding, and that given a graph, testing if there exists a surface such that the graph admits a rectilinear embedding in that surface are NP-complete problems and hence the corresponding optimization problems are NP-hard.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_56
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.560 Geometry
ID Code:73

Repository Staff Only: item control page


D. Dolev and R. Trickey. On linear area embedding of planar graphs. Technical Report STAN-CS-81-876, 1981.

M. Fréchet and Ky Fan. Initiation to Combinatorial Topology. Weber and Schmidt, 1967.

M. R. Garey and D. S. Johnson. Computers and Intractability: a guide to the theory of NP-completeness. Freeman, 1979.

A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. In R. Tamassia and I. G. Tollis, editors, Graph Drawing 94, Lecture Notes in Computer Science, pages 286-297. Springer-Verlag, 1994.

J. L. Gross and T. W. Tucker. Topological graph theory. John Wiley & Sons, 1987.

T. A. J. Nicholson. Permutation procedure for minimizing the number of crossings in a network. Proc. Inst. Elec. Eng., 115:21-26, 1968.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. Siam J. Comput., 16(3):421-444, 1987.

C. Thomassen. The graph genus problem in NP-complete. Journal of Algorithmus, 10:568-576, 1989.