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: |