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.
Repository Staff Only: item control page