Mostrar el registro sencillo del ítem
Ponencia
Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
dc.creator | Cabello Justo, Sergio | es |
dc.date.accessioned | 2017-03-01T13:26:37Z | |
dc.date.available | 2017-03-01T13:26:37Z | |
dc.date.issued | 2004 | |
dc.identifier.citation | Cabello Justo, S. (2004). Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. En 20th European Workshop on Computational Geometry, Sevilla. | |
dc.identifier.uri | http://hdl.handle.net/11441/55055 | |
dc.description.abstract | Let G = (V, E) be a graph with n vertices and let P be a set of n points in the plane. We show that deciding whether there is a planar straight-line embedding of G such that the vertices V are embedded onto the points P is NP-complete, even when G is 2-connected and 2-outerplanar. This settles an open problem posed in [P. Bose. On embedding an outer-planar graph in a point set. Comput. Geom. Theory Appl., 23:303-312, November 2002. A preliminary version appeared in Graph Drawing (Proc. GD ’97), LNCS 1353, pg. 25-36, F. Brandenberg, D. Eppstein, M.T. Goodrich, S.G. Kobourov, G. Liotta, and P. Mutzel. Selected open problems in graph drawing. In Graph Drawing (Proc. GD’03), LNCS, 2003. To appear y M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115–129, 2002. A preliminary version appeared in Graph Drawing (Proc. GD ’99), LNCS 1731, pg. 165–174]. | es |
dc.description.sponsorship | Cornelis Lely Stichting | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | 20th European Workshop on Computational Geometry (2004). | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Planar embeddability of the vertices of a graph using a fixed point set is NP-hard | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
idus.format.extent | 4 p. | es |
dc.eventtitle | 20th European Workshop on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Planar embeddability of the ... | 122.3Kb | ![]() | Ver/ | |