Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time

2005/12/15 by Kutz, Martin
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.cs/0512064

Abstract

We present an algorithm that computes a shortest non-contractible and a shortest non-separating cycle on an orientable combinatorial surface of bounded genus in O(n log n) time, where n denotes the complexity of the surface. This solves a central open problem in computational topology, improving upon the current-best O(n^3/2)-time algorithm by Cabello and Mohar (ESA 2005). Our algorithm uses universal-cover constructions to find short cycles and makes extensive use of existing tools from the field.

Related

• Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
• Computing shortest closed curves on non-orientable surfaces
• Computing the second and third systoles of a combinatorial surface
• Holiest Minimum-Cost Paths and Flows in Surface Graphs
• Minimum cycle and homology bases of surface embedded graphs