Informace o publikaci
Computing the Stretch of an Embedded Graph
Název česky | Výpočet roztažení nakresleného grafu |
---|---|
Autoři | |
Rok publikování | 2013 |
Druh | Článek ve sborníku |
Konference | XV Spanish Meeting on Computational Geometry |
Fakulta / Pracoviště MU | |
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: |