dc.contributor.editor | Díaz Báñez, José Miguel | es |
dc.contributor.editor | Garijo Royo, Delia | es |
dc.contributor.editor | Márquez Pérez, Alberto | es |
dc.contributor.editor | Urrutia Galicia, Jorge | es |
dc.creator | Cabello Justo, Sergio | es |
dc.creator | Chimani, Markus | es |
dc.creator | Hliněný, Petr | es |
dc.date.accessioned | 2017-05-18T11:26:17Z | |
dc.date.available | 2017-05-18T11:26:17Z | |
dc.date.issued | 2013 | |
dc.identifier.citation | Cabello Justo, S., Chimani, M. y Hliněný, P. (2013). Computing the stretch of an embedded graph. En XV Spanish Meeting on Computational Geometry, Sevilla. | |
dc.identifier.uri | http://hdl.handle.net/11441/60027 | |
dc.description.abstract | Let G be a graph embedded in an orientable surface Σ, possibly with edge weights, and denote by len(γ) the length (the number of edges or the sum of the edge weights) of a cycle γ in G. The stretch of a graph embedded on a surface is the minimum of len(α)· len(β) over all pairs of cycles α and β that cross exactly once. We provide an algorithm to compute the stretch of an
embedded graph in time O(g4n log n) with high probability, or in time O(g4n log2 n) in the worst case, where g is the genus of the surface Σ and n is the
number of vertices in G. | es |
dc.description.sponsorship | Slovenian Research Agency | es |
dc.description.sponsorship | European Science Foundation | es |
dc.description.sponsorship | Carl-Zeiss-Foundation | es |
dc.description.sponsorship | Czech Science Foundation | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | XV Spanish Meeting on Computational Geometry (2013), pp. 47-50. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Computing the stretch of an embedded graph | es |
dc.type | info:eu-repo/semantics/conferenceObject | 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 II | |
dc.relation.projectID | J1-4106 | es |
dc.relation.projectID | GReGAS | es |
dc.relation.projectID | GIG/11/E023 | es |
dc.relation.publisherversion | http://congreso.us.es/ecgeometry/proceedingsECG2013.pdf | es |
idus.format.extent | 4 p. | es |
dc.publication.initialPage | 47 | es |
dc.publication.endPage | 50 | es |
dc.eventtitle | XV Spanish Meeting on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |