Configurations with few crossings in topological graphs

DOI10.1016/J.COMGEO.2006.06.001MaRDI QIDQ876504zbMATH OpenOpenAlexFDO

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

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 algorithmsfixed-parameter algorithmscrossing minimizationMonte-Carlo algorithms

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Computation
• On topological graphs with at most four crossings per edge
• Graph Drawing
• On edges crossing few other edges in simple topological complete graphs
• Noncrossing Subgraphs in Topological Layouts
• Configuration spaces of graphs
• Structure of graphs with locally restricted crossings
• On the crossing number of almost planar graphs
• On the Crossing Number of Almost Planar Graphs
• Publication:4552009

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A Short Proof of the Factor Theorem for Finite Graphs
• Algorithms and Computation
• Fundamentals of Computation Theory
• Noncrossing Subgraphs in Topological Layouts
• Reconstructing sets of orthogonal line segments in the plane
• The complexity of detecting crossingfree configurations in the plane

Cited in

(7)

• Non-crossing geometric Steiner arborescences
• Maximum weighted matching with few edge crossings for 2-layered bipartite graph
• Algorithms and Computation
• Parameterized analysis and crossing minimization problems
• Crossing Stars in Topological Graphs
• Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
• Noncrossing subgraphs in the topological graph \(K_{3,3}\)

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

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