Crossing numbers of graphs with rotation systems

DOI10.1007/S00453-009-9343-YMaRDI QIDQ548653zbMATHOpenAlexFDO

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

NP-completenesstournamentscrossing numberindependent odd crossing numberodd crossing numberrotation system

Mathematics Subject Classification ID

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

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

• 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?)
• 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 NP-Complete
• Crossing number is hard for cubic graphs
• Graphs on surfaces
• 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 on Surfaces
• Removing even crossings
• Removing independently even crossings
• Some simplified NP-complete graph problems
• Toward a theory of crossing numbers
• Which crossing number is it anyway?

Cited in

(15)

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

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)