The complexity of detecting crossingfree configurations in the plane
From MaRDI portal
Publication:1317860
DOI10.1007/BF01990536zbMath0797.68080OpenAlexW2127145740MaRDI QIDQ1317860
Gerhard J. Woeginger, Klaus Jansen
Publication date: 22 March 1994
Published in: BIT (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01990536
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items (14)
Covering oriented points in the plane with orthogonal polygons is NP-complete ⋮ Reconstruction of Weakly Simple Polygons from Their Edges ⋮ Parameterized analysis and crossing minimization problems ⋮ Configurations with few crossings in topological graphs ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ Covering points with orthogonal polygons ⋮ Fast enumeration algorithms for non-crossing geometric graphs ⋮ Enumerating constrained non-crossing minimally rigid frameworks ⋮ Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees ⋮ Reconstructing polygons from scanner data ⋮ A Bottleneck Matching Problem with Edge-Crossing Constraints ⋮ Connected Rectilinear Graphs on Point Sets ⋮ Connecting the dots (with minimum crossings) ⋮ Non-crossing geometric steiner arborescences
Cites Work
This page was built for publication: The complexity of detecting crossingfree configurations in the plane