Computing the Stretch of an Embedded Graph
| Authors | |
|---|---|
| Year of publication | 2013 |
| Type | Article in Proceedings |
| Conference | XV Spanish Meeting on Computational Geometry |
| MU Faculty or unit | |
| Citation | |
| Web | sbornik |
| Field | General mathematics |
| Description | 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)$. |
| Related projects: |