Crossing numbers of graphs with rotation systems
DOI10.1007/S00453-009-9343-YzbMATH Open1218.68087OpenAlexW2019336795MaRDI QIDQ548653FDOQ548653
Marcus Schaefer, D. Štefankovič, Michael J. Pelsmajer
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graphs on surfaces
- Some simplified NP-complete graph problems
- Crossing Number is NP-Complete
- On a cyclic string-to-string correction problem
- Crossing number is hard for cubic graphs
- An Extension of the String-to-String Correction Problem
- Title not available (Why is that?)
- Recognizing string graphs in NP
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Removing Even Crossings on Surfaces
- An optimality criterion for the crossing number
- Removing Independently Even Crossings
- Title not available (Why is that?)
- Bimodal Crossing Minimization
- Toward a theory of crossing numbers
- Removing even crossings
Cited In (11)
- Rotation numbers for unions of circuits
- Deciding Parity of Graph Crossing Number
- Title not available (Why is that?)
- Mathematical Foundations of Computer Science 2004
- Which crossing number is it anyway?
- Order on order types
- Adjacent Crossings Do Matter
- Parameterized analysis and crossing minimization problems
- Hardness of approximation for crossing number
- Simple realizability of complete abstract topological graphs simplified
- The crossing number of twisted graphs
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)
