J 2014

Computing the stretch of an embedded graph

CABELLO, Sergio, Markus CHIMANI a Petr HLINĚNÝ

Základní údaje

Originální název

Computing the stretch of an embedded graph

Autoři

CABELLO, Sergio (724 Španělsko), Markus CHIMANI (40 Rakousko) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2014, 0895-4801

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.654

Kód RIV

RIV/00216224:14330/14:00074093

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000343230800019

Klíčová slova anglicky

topological graph theory; embedded graph; crossings; nonseparating cycle; homology basis

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 14. 11. 2014 13:08, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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)).

Návaznosti

GEGIG/11/E023, projekt VaV
Název: Kreslení grafů a jejich geometrické reprezentace (Akronym: GraDR)
Investor: Grantová agentura ČR, Graph Drawings and Representations