The complexity of detecting crossingfree configurations in the plane

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

zbMATH Keywords

geometrycomputational complexityalgorithmic complexitycrossingfree spanning treesplanar layouts

Mathematics Subject Classification ID

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

• Unnamed Item
• Unnamed Item
• Reconstructing sets of orthogonal line segments in the plane
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Noncrossing Subgraphs in Topological Layouts
• Information Dissemination in Trees

This page was built for publication: The complexity of detecting crossingfree configurations in the plane