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

 

Advanced Search
 
Opened Access Embedding a graph in the grid of a surface with the minimum number of bends is NP-hard
Cites

Show item statistics
Icon
Export to
Author: Garrido Vizuete, María de los Angeles
Márquez Pérez, Alberto
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 1997
Published in: Graph Drawing, 1353, 124-133.
Document type: Article
Abstract: 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.
Cite: 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.
Size: 500.1Kb
Format: PDF

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

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

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)