Mostrar el registro sencillo del ítem
Artículo
Embedding a graph in the grid of a surface with the minimum number of bends is NP-hard
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 |
dcterms.identifier | https://ror.org/03yxnpp24 | |
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 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Embedding a graph.pdf | 500.1Kb | [PDF] | Ver/ | |