2016-01-272016-01-271997Garrido Vizuete, M.d.l.A. y Márquez Pérez, A. (1997). Embedding a graph in the grid of a surface with the minimum number of bends is NP-hard. Graph Drawing, 1353 (1997), 124-133.http://hdl.handle.net/11441/33425This 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.application/pdfengAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Theory of ComputationDiscrete MathematicsComputer-Aided Engineering (CAD, CAE) and DesignDiscrete Mathematics in Computer ScienceCombinatoricsAlgorithm Analysis and Problem Complexityinfo:eu-repo/semantics/articleinfo:eu-repo/semantics/openAccesshttp://dx.doi.org/10.1007/3-540-63938-1_56https://idus.us.es/xmlui/handle/11441/33425