Tightening Curves on Surfaces Monotonically with Applications
Abstract
We prove the first polynomial bound on the number of monotonic homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number of crossings in the curve is not allowed to increase at any time during the process. The best known upper bound before was exponential, which can be obtained by combining the algorithm of De Graaf and Schrijver [ J. Comb. Theory Ser. B , 1997] together with an exponential upper bound on the number of possible surface maps. To obtain the new upper bound, we apply tools from hyperbolic geometry, as well as operations in graph drawing algorithms—the cluster and pipe expansions—to the study of curves on surfaces.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 31, 2022
- Source ID
- 10.1145/3558097
Entities
People
- Arnaud de Mesmay
- Hsien-Chih Chang
Organizations
- Dartmouth College
- ESIEE Paris
- National Science Foundation