COMPUTING THE STRETCH OF AN EMBEDDED GRAPH

Autor(en): Cabello, Sergio
Chimani, Markus 
Hlineny, Petr
Stichwörter: crossings; embedded graph; homology basis; Mathematics; Mathematics, Applied; nonseparating cycle; PLANAR CROSSING NUMBERS; SURFACE; topological graph theory
Erscheinungsdatum: 2014
Herausgeber: SIAM PUBLICATIONS
Enthalten in: SIAM JOURNAL ON DISCRETE MATHEMATICS
Band: 28
Ausgabe: 3
Startseite: 1391
Seitenende: 1401
Zusammenfassung: 
Let G be a graph embedded in an orientable surface Sigma, possibly with edge weights, and denote by len(gamma) 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(alpha) . len(beta) over all pairs of cycles alpha and beta that cross exactly once. We provide two algorithms to compute the stretch of an embedded graph, each based on a different principle. The first algorithm is based on surgery and computes the stretch in time O(g(4)n log n) with high probability, or in time O(g(4)n log(2) n) in the worst case, where g is the genus of the surface S and n is the number of vertices in G. The second algorithm is based on using a short homology basis and computes the stretch in time O(n(2) log n n(2)g ng(3)).
ISSN: 08954801
DOI: 10.1137/130945636

Show full item record

Page view(s)

6
Last Week
0
Last month
1
checked on Jun 15, 2024

Google ScholarTM

Check

Altmetric