Crossing numbers of graphs with rotation systems

DOI10.1007/s00453-009-9343-yzbMath1218.68087OpenAlexW2019336795MaRDI QIDQ548653

Marcus Schaefer, Michael J. Pelsmajer, Daniel Š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

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

Related Items (6)

Order on order types ⋮ Parameterized analysis and crossing minimization problems ⋮ Deciding Parity of Graph Crossing Number ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ Hardness of approximation for crossing number ⋮ Adjacent Crossings Do Matter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Removing even crossings
• On a cyclic string-to-string correction problem
• Some simplified NP-complete graph problems
• A successful concept for measuring non-planarity of graphs: The crossing number.
• Which crossing number is it anyway?
• Odd crossing number and crossing number are not the same
• Crossing number is hard for cubic graphs
• Crossing Number is NP-Complete
• Removing Even Crossings on Surfaces
• An optimality criterion for the crossing number
• Removing Independently Even Crossings
• Bimodal Crossing Minimization
• An Extension of the String-to-String Correction Problem
• Toward a theory of crossing numbers
• Recognizing string graphs in NP

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