Splitting (complicated) surfaces is hard

DOI10.1016/J.COMGEO.2007.10.010zbMATH Open1152.65026OpenAlexW2199785256MaRDI QIDQ934027FDOQ934027

Authors: Éric Colin de Verdière, Jeff Erickson, Francis Lazarus, Kim Whittlesey, Erin W. Chambers 

Publication date: 29 July 2008

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2007.10.010

Recommendations

• Tightening nonsimple paths and cycles on surfaces
• Computing the shortest essential cycle
• Optimally cutting a surface into a disk
• Optimally cutting a surface into a disk
• Finding shortest contractible and shortest separating cycles in embedded graphs

zbMATH Keywords

computational topologyhomotopycyclelooporientable surfacecombinatorial surfacescurve on surfacesplitting curvesurface splitting

Mathematics Subject Classification ID

Geometric structures on manifolds of high or arbitrary dimension (57N16) Computer-aided design (modeling of curves and surfaces) (65D17)

Cites Work

• Title not available (Why is that?)
• Finding the k Shortest Paths
• Graphs on surfaces
• Hamilton Paths in Grid Graphs
• Topology for Computing
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• The Discrete Geodesic Problem
• Title not available (Why is that?)
• SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
• Optimally cutting a surface into a disk
• Greedy optimal homotopy and homology generators
• Title not available (Why is that?)
• Tightening non-simple paths and cycles on surfaces
• Computing a canonical polygonal schema of an orientable triangulated surface
• Many distances in planar graphs
• Optimal system of loops on an orientable surface
• Algorithms – ESA 2005
• Graph Drawing

Cited In (14)

• Computing intersection numbers and bases of cohomology groups for triangulated closed three-dimensional manifolds
• Topologically trivial closed walks in directed surface graphs
• Minimum decomposition of a digital surface into digital plane segments is NP-hard
• Optimal system of loops on an orientable surface
• Minimal Decomposition of a Digital Surface into Digital Plane Segments Is NP-Hard
• Computing the shortest essential cycle
• Counting and sampling minimum cuts in genus \(g\) graphs
• Title not available (Why is that?)
• Minimum Cuts in Surface Graphs
• Graph Drawing
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Irreducible triangulations of surfaces with boundary
• Global minimum cuts in surface embedded graphs
• Non total-unimodularity neutralized simplicial complexes

This page was built for publication: Splitting (complicated) surfaces is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q934027)