Logo

Login

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. [Conference Paper]

Full text not available from this repository.

Abstract

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
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
Deposited By:Martinez Leon, Victoria
Deposited On:27 Oct 2004
Last Modified:28 Apr 2009 14:29

Repository Staff Only: item control page

References

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

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

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

4. 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.

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

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

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.