Configurations with few crossings in topological graphs

DOI10.1016/j.comgeo.2006.06.001zbMath1117.05029OpenAlexW2161036821MaRDI QIDQ876504

Étienne Schramm, Christian Knauer, Alexander Wolff, Andreas Spillner

Publication date: 18 April 2007

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

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

zbMATH Keywords

approximation algorithmscrossing minimizationfixed-parameter algorithmsMonte-Carlo algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Parameterized analysis and crossing minimization problems ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ Maximum weighted matching with few edge crossings for 2-layered bipartite graph ⋮ Non-crossing geometric steiner arborescences

Cites Work

• Unnamed Item
• Reconstructing sets of orthogonal line segments in the plane
• The complexity of detecting crossingfree configurations in the plane
• Noncrossing Subgraphs in Topological Layouts
• Fundamentals of Computation Theory
• A Short Proof of the Factor Theorem for Finite Graphs
• Algorithms and Computation

This page was built for publication: Configurations with few crossings in topological graphs