Embedding a Graph in the Grid of a Surface with the Minimum Number of Bends Is NPhardGarrido, M. Ángeles and Márquez, Alberto (1998) Embedding a Graph in the Grid of a Surface with the Minimum Number of Bends Is NPhard. In: Graph Drawing 5th International Symposium, GD '97, September 1820, 1997 , pp. 124133(Official URL: http://dx.doi.org/10.1007/3540639381_56). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540639381_56
AbstractThis paper is devoted to the study of graph embeddings in the grid of nonplanar 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 NPcomplete problems and hence the corresponding optimization problems are NPhard.
Actions (login required)
