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 , pp. 124-133(Official URL: http://dx.doi.org/10.1007/3-540-63938-1_56).

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
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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/73

Actions (login required)

View Item View Item