| Identifikační kód | RIV/00216224:14330/14:00074093 |
|---|
| Název v anglickém jazyce | Computing the stretch of an embedded graph |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | B - Fyzika a matematika |
|---|
| Obor | BA - Obecná matematika |
|---|
| Rok uplatnění | 2014 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 3 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Sergio Cabello (státní příslušnost: ES - Španělské království)
Markus Chimani (státní příslušnost: AT - Rakouská republika)
Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646) |
|---|
| Popis výsledku v anglické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)). |
|---|
| Klíčová slova oddělená středníkem | topological graph theory; embedded graph; crossings; nonseparating cycle; homology basis |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1137/130945636 |
|---|