Repositorio de producción científica de la Universidad de Sevilla

Embedding a graph in the grid of a surface with the minimum number of bends is NP-hard

 

Búsqueda avanzada
 
Opened Access Embedding a graph in the grid of a surface with the minimum number of bends is NP-hard
Citas

Estadísticas
Icon
Exportar a
Autor: Garrido Vizuete, María de los Angeles
Márquez Pérez, Alberto
Departamento: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Fecha: 1997
Publicado en: Graph Drawing, 1353, 124-133.
Tipo de documento: Artículo
Resumen: 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.
Cita: Garrido 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.
Tamaño: 500.1Kb
Formato: PDF

URI: http://hdl.handle.net/11441/33425

DOI: http://dx.doi.org/10.1007/3-540-63938-1_56

Salvo que se indique lo contrario, los contenidos de esta obra estan sujetos a la licencia de Creative Commons: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones