Recognizing weakly simple polygons

DOI10.1007/s00454-017-9918-3zbMath1454.68151OpenAlexW2309657040MaRDI QIDQ1688854

Hugo A. Akitaya, Jeff Erickson, Greg Aloupis, Csaba D. Tóth

Publication date: 11 January 2018

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5900/

zbMATH Keywords

perturbationsimple polygoncombinatorial embedding

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Related Items

Minimum Cuts in Surface Graphs, Reconstruction of Weakly Simple Polygons from Their Edges, Atomic Embeddability, Clustered Planarity, and Thickenability, Finding weakly simple closed quasigeodesics on polyhedral spheres, Embedding graphs into embedded graphs, Piercing pairwise intersecting geodesic disks, Crossing minimization in perturbed drawings, Crossing minimization in perturbed drawings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polygons: Meister was right and Poinsot was wrong but prevailed
• On embedding a cycle in a plane graph
• Triangulating a simple polygon in linear time
• On approximability by embeddings of cycles in the plane.
• \(c\)-planarity of embedded cyclic \(c\)-graphs
• When can you fold a map?
• Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths
• A Census of Plane Graphs with Polyline Edges
• Dynamic LCA Queries on Trees
• Detecting Weakly Simple Polygons