Splitting (complicated) surfaces is hard
type: Item
instance of: scholarly article
title: Splitting (complicated) surfaces is hard
zbMATH Open document ID: 1152.65026
author: Éric Colin de Verdière
author: Jeff Erickson
author: Francis Lazarus
author: Kim Whittlesey
author: Erin W. Chambers
published in: Computational Geometry
publication date: 2008-07-29T00:00:00Z
review text: The authors solve the optimization problem of finding the shortest simple cycle that separates an orientable surface (2-manifold with boundary) into two topologically non-trivial components. The cycle is a continuous map of the unit circle on the considered surface. Firstly, the proof that computing the shortest splitting cycle on a given surface is NP-hard is given and then the algorithm for computation of the shortest splitting cycle is described and its hardness is discussed. The authors also show that the shortest splitting problem is fixed-parameter tractable with respect to the genus and the number of boundary components of the surface. The problem of finding the shortest cycle that separates the surface into two surfaces of prescribed topology is considered, too.
reviewed by: Ivana Linkeová
Mathematics Subject Classification ID: 65D17
Mathematics Subject Classification ID: 57N16
zbMATH DE Number: 5304599
zbMATH Keywords: orientable surface
zbMATH Keywords: surface splitting
zbMATH Keywords: cycle
zbMATH Keywords: splitting curve
zbMATH Keywords: curve on surface
zbMATH Keywords: loop
zbMATH Keywords: computational topology
zbMATH Keywords: combinatorial surfaces
zbMATH Keywords: homotopy
MaRDI profile type: MaRDI publication profile
full work available at URL: j.comgeo.2007.10.010
OpenAlex ID: W2199785256
cites work: Many distances in planar graphs
cites work: Algorithms – ESA 2005
cites work: SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
cites work: Tightening non-simple paths and cycles on surfaces
cites work: Graph Drawing
cites work: Optimal system of loops on an orientable surface
cites work: Finding the k Shortest Paths
cites work: Optimally cutting a surface into a disk
cites work: Greedy optimal homotopy and homology generators
cites work: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
cites work: Q4819371
cites work: Hamilton Paths in Grid Graphs
cites work: Q3601569
cites work: Computing a canonical polygonal schema of an orientable triangulated surface
cites work: The Discrete Geodesic Problem
cites work: Graphs on surfaces
cites work: Q3135833
cites work: Topology for Computing
DOI: 10.1016/J.COMGEO.2007.10.010
description: scientific article; zbMATH DE number 5304599