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

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

(16)

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