Finding a shortest curve that separates few objects from many

DOI10.4230/LIPICS.SOCG.2025.18MaRDI QIDQ7312658zbMATH OpenFDO

Authors Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, Günter Rote

Publication date 11 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2025.18

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A generalization of Dijkstra's algorithm
• A new proof of 3-colorability of Eulerian triangulations
• Computing shortest closed curves on non-orientable surfaces
• Detecting and decomposing self-overlapping curves
• Detecting weakly simple polygons
• Enclosing points with geometric objects
• Finding minimum area \(k\)-gons
• Geometric Knapsack problems
• Geometric multicut: shortest fences for separating groups of objects in the plane
• Minimum Cuts in Surface Graphs
• On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs
• Recognizing weakly simple polygons
• Reconstruction of Weakly Simple Polygons from Their Edges
• Splitting (complicated) surfaces is hard
• The complexity of computing minimum separating polygons

This page was built for publication: Finding a shortest curve that separates few objects from many

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