Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414317 | Computational Geometry | 2008 | 17 Pages |
Abstract
Let M be an orientable combinatorial surface. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither of which is homeomorphic to a disk. In other words, splitting cycles are simple, separating, and non-contractible. We prove that finding the shortest splitting cycle on a combinatorial surface is NP-hard but fixed-parameter tractable with respect to the surface genus g and the number of boundary components b of the surface. Specifically, we describe an algorithm to compute the shortest splitting cycle in (g+b)O(g+b)nlogn time, where n is the complexity of the combinatorial surface.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics