Crossing numbers of graphs with rotation systems
Publication:548653
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
NP-completenesstournamentscrossing numberindependent odd crossing numberodd crossing numberrotation system
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)
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
