Crossing numbers of graphs with rotation systems

DOI10.1007/S00453-009-9343-YMaRDI QIDQ548653zbMATH OpenOpenAlexFDO

Authors Michael J. Pelsmajer, Marcus Schaefer, D. Štefankovič

Publication date 30 June 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-009-9343-y

zbMATH Keywords

crossing numberindependent odd crossing numberNP-completenessodd crossing numberrotation systemtournaments

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Crossing Number of Graphs with Rotation Systems
• Crossing number is hard for cubic graphs
• Mathematical Foundations of Computer Science 2004
• Which crossing number is it anyway?
• Crossing Number is NP-Complete

Cites work

• A successful concept for measuring non-planarity of graphs: The crossing number.
• Additive combinatorics
• An Extension of the String-to-String Correction Problem
• An optimality criterion for the crossing number
• Bimodal Crossing Minimization
• Crossing number is hard for cubic graphs
• Crossing Number is NP-Complete
• Graphs on surfaces
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3557227 (Why is no real title available?)
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 1454642 (Why is no real title available?)
• Minor-monotone crossing number
• Odd crossing number and crossing number are not the same
• On a cyclic string-to-string correction problem
• Recognizing string graphs in NP
• Removing even crossings
• Removing Even Crossings on Surfaces
• Removing independently even crossings
• Some simplified NP-complete graph problems
• Toward a theory of crossing numbers
• Which crossing number is it anyway?

Cited in

(18)

• The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph
• Order on order types
• Which crossing number is it anyway?
• Hardness of approximation for crossing number
• The crossing number of twisted graphs
• Parameterized analysis and crossing minimization problems
• Simple realizability of complete abstract topological graphs simplified
• Crossing number is hard for cubic graphs
• Crossing Number is NP-Complete
• Rotation numbers for unions of circuits
• scientific article; zbMATH DE number 5130834 (Why is no real title available?)
• Deciding Parity of Graph Crossing Number
• Mathematical Foundations of Computer Science 2004
• Crossing Number of Graphs with Rotation Systems
• Adjacent Crossings Do Matter
• Drawn tree decomposition: new approach for graph drawing problems
• Complexity of anchored crossing number and crossing number of almost planar graphs
• A unified FPT framework for crossing number problems

This page was built for publication: Crossing numbers of graphs with rotation systems

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