The Crossing Number of Graphs: Theory and Computation

DOI10.1007/978-3-642-03456-5_21MaRDI QIDQ3644730zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

approximationscomputational geometrycrossing number of graphsexact computationsrectilinear crossing numbersurvey article

Mathematics Subject Classification ID

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

Recommendations

• SOFSEM 2005: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 1054768
• The graph crossing number and its variants: a survey
• Crossing numbers
• The rectilinear crossing number of K_n: closing in (or are we?)

Cites work

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

Cited in

(32)

• Crossings, colorings, and cliques
• Special numbers of crossings for complete graphs
• The crossing number of a graph on a compact 2-manifold
• The number of crossings in multigraphs with no empty lens
• The graph crossing number and its variants: a survey
• Crossing number for graphs with bounded pathwidth
• The crossing number of twisted graphs
• A crossing lemma for multigraphs
• Counting the number of crossings in geometric graphs
• On the average crosscap number. II: Bounds for a graph
• The rectilinear crossing number of K_n: closing in (or are we?)
• Survey of the crossing number of graphs
• The crossing number of chordal ring networks
• Graph minors and the crossing number of graphs
• On the crossing number of some complete multipartite graphs
• Do we really understand the crossing numbers?
• Crossing numbers
• scientific article; zbMATH DE number 1792068 (Why is no real title available?)
• Crossing numbers of graphs
• scientific article; zbMATH DE number 2170413 (Why is no real title available?)
• Crossing numbers of random graphs
• scientific article; zbMATH DE number 1894431 (Why is no real title available?)
• scientific article; zbMATH DE number 7278018 (Why is no real title available?)
• A survey of graphs with known or bounded crossing numbers
• Improving the crossing lemma by finding more crossings in sparse graphs
• Crossing Numbers and Parameterized Complexity
• scientific article; zbMATH DE number 969978 (Why is no real title available?)
• SOFSEM 2005: Theory and Practice of Computer Science
• On crossing numbers of geometric proximity graphs
• Heuristics for exact 1-planarity testing
• Heuristics for exact 1-planarity testing
• On the crossing number of complete graphs

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

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