Computing the stretch of an embedded graph

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

CABELLO Sergio CHIMANI Markus HLINĚNÝ Petr

Rok publikování 2014
Druh Článek v odborném periodiku
Časopis / Zdroj SIAM Journal on Discrete Mathematics
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1137/130945636
Obor Obecná matematika
Klíčová slova topological graph theory; embedded graph; crossings; nonseparating cycle; homology basis
Popis 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)).
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.