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
 

Show simple item record

dc.creator Garrido Vizuete, María de los Angeles
dc.creator Márquez Pérez, Alberto
dc.date.accessioned 2016-01-27T12:14:32Z
dc.date.available 2016-01-27T12:14:32Z
dc.date.issued 1997
dc.identifier.citation 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. es
dc.identifier.uri http://hdl.handle.net/11441/33425
dc.description.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. es
dc.format application/pdf es
dc.language.iso eng es
dc.relation.ispartof Graph Drawing, 1353, 124-133. es
dc.rights Attribution-NonCommercial-NoDerivatives 4.0 Internacional *
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/4.0/ *
dc.subject Theory of Computation es
dc.subject Discrete Mathematics es
dc.subject Computer-Aided Engineering (CAD, CAE) and Design es
dc.subject Discrete Mathematics in Computer Science es
dc.subject Combinatorics es
dc.subject Algorithm Analysis and Problem Complexity es
dc.title Embedding a graph in the grid of a surface with the minimum number of bends is NP-hard es
dc.type info:eu-repo/semantics/article es
dc.type.version info:eu-repo/semantics/publishedVersion es
dc.rights.accessrights info:eu-repo/semantics/openAccess es
dc.contributor.affiliation Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) es
dc.identifier.doi http://dx.doi.org/10.1007/3-540-63938-1_56 es
dc.journaltitle Graph Drawing es
dc.publication.volumen 1353 es
dc.publication.issue 1997 es
dc.publication.initialPage 124 es
dc.publication.endPage 133 es
dc.identifier.idus https://idus.us.es/xmlui/handle/11441/33425
Size: 500.1Kb
Format: PDF

This item appears in the following Collection(s)

Show simple item record