Computing the stretch of an embedded graph

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F14%3A00074093" target="_blank" >RIV/00216224:14330/14:00074093 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1137/130945636" target="_blank" >http://dx.doi.org/10.1137/130945636</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/130945636" target="_blank" >10.1137/130945636</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Computing the stretch of an embedded graph

Popis výsledku v původním jazyce

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 thestretch 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 computesthe stretch in time O(n(2) log n + n(2)g + ng(3)).

Název v anglickém jazyce

Computing the stretch of an embedded graph

Popis výsledku anglicky

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 thestretch 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 computesthe stretch in time O(n(2) log n + n(2)g + ng(3)).

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Kreslení grafů a jejich geometrické reprezentace</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

—

Svazek periodika

28

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

11

Strana od-do

1391-1401

Kód UT WoS článku

000343230800019

EID výsledku v databázi Scopus

—