Repositorio de producción científica de la Universidad de Sevilla

Computing the stretch of an embedded graph


Advanced Search
Opened Access Computing the stretch of an embedded graph
Show item statistics
Export to
Author: Cabello Justo, Sergio
Chimani, Markus
Hliněný, Petr
Coordinator/Director: Díaz Báñez, José Miguel
Garijo Royo, Delia
Márquez Pérez, Alberto
Urrutia Galicia, Jorge
Date: 2013
Published in: XV Spanish Meeting on Computational Geometry (2013), p 47-50
Document type: Presentation
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.
Size: 866.2Kb
Format: PDF


See editor´s version

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

This item appears in the following Collection(s)