Computing the Stretch of an Embedded Graph

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CABELLO Sergio CHIMANI Markus HLINĚNÝ Petr

Year of publication 2013
Type Article in Proceedings
Conference XV Spanish Meeting on Computational Geometry
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.