The Crossing Number of Graphs: Theory and Computation

DOI10.1007/978-3-642-03456-5_21zbMath1257.05029DBLPconf/birthday/Mutzel09OpenAlexW1808714161WikidataQ56977210 ScholiaQ56977210MaRDI QIDQ3644730

Petra Mutzel

Publication date: 12 November 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03456-5_21

zbMATH Keywords

approximationsrectilinear crossing numbercomputational geometrysurvey articleexact computationscrossing number of graphs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Vertex insertion approximates the crossing number of apex graphs
• A framework for solving VLSI graph layout problems
• On the crossing number of complete graphs
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• A branch-and-cut approach to the crossing number problem
• Some provably hard crossing number problems
• Improved bounds for planar \(k\)-sets and related problems
• A successful concept for measuring non-planarity of graphs: The crossing number.
• Inserting an edge into a planar graph
• Which crossing number is it anyway?
• Crossing number, pair-crossing number, and expansion
• Odd crossing number and crossing number are not the same
• Crossing Number is NP-Complete
• Removing Even Crossings on Surfaces
• A New Approach to Exact Crossing Minimization
• On the Crossing Number of Almost Planar Graphs
• Crossing and Weighted Crossing Number of Near-Planar Graphs
• New results on rectilinear crossing numbers and plane embeddings
• Bounds for rectilinear crossing numbers
• On the number of sums and products
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• The Rectilinear Crossing Number of a Complete Graph and Sylvester's "Four Point Problem" of Geometric Probability
• The crossing number of K₁₁ is 100
• Toward a theory of crossing numbers
• On a problem of P. Turan concerning graphs

This page was built for publication: The Crossing Number of Graphs: Theory and Computation