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.
Název česky Výpočet roztažení nakresleného grafu
Autoři

CABELLO Sergio CHIMANI Markus HLINĚNÝ Petr

Rok publikování 2013
Druh Článek ve sborníku
Konference XV Spanish Meeting on Computational Geometry
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www sbornik
Obor Obecná matematika
Popis 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 $\Sigma$ 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^2g + 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.