## 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)
Full text not available from this repository. ## AbstractThis 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 References |