Computing the stretch of an embedded graph

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Computing the stretch of an embedded graph
Original language description
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)).
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/GEGIG%2F11%2FE023" target="_blank" >GEGIG/11/E023: Graph Drawings and Representations</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)