Published May 18, 2017 | Version v1
Publication Metadata-only

Computing the stretch of an embedded graph

Creators

Contributors

Description

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.

Abstract

Slovenian Research Agency

Abstract

European Science Foundation

Abstract

Carl-Zeiss-Foundation

Abstract

Czech Science Foundation

Additional details

Identifiers

URL
https://idus.us.es/handle/11441/60027
URN
urn:oai:idus.us.es:11441/60027

Origin repository

Origin repository
USE