Crossing Numbers and Parameterized Complexity
DOI10.1007/978-3-540-77537-9_6zbMATH Open1137.68502OpenAlexW1708570965MaRDI QIDQ5452207FDOQ5452207
Authors: Michael J. Pelsmajer, Marcus Schaefer, D. Štefankovič 
Publication date: 25 March 2008
Published in: Graph Drawing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-77537-9_6
Recommendations
- Hardness of approximation for crossing number
- On the complexity of crossings in permutations
- Crossing Number is NP-Complete
- The Crossing Number of Graphs: Theory and Computation
- On the Pseudolinear Crossing Number
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- The complexity of detecting crossingfree configurations in the plane
- The Parameterized Complexity of Counting Problems
- Exact crossing number parameterized by vertex cover
- scientific article; zbMATH DE number 1054768
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Computing crossing numbers in quadratic time
- Title not available (Why is that?)
- String graphs requiring exponential representations
- Which crossing number is it anyway?
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Drawing
- Note on the pair-crossing number and the odd-crossing number
- Decidability of string graphs
Cited In (16)
- Some provably hard crossing number problems
- On the Pseudolinear Crossing Number
- Recognizing and drawing IC-planar graphs
- Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
- Graph Drawing
- Which crossing number is it anyway?
- Exact crossing number parameterized by vertex cover
- Crossing number is hard for kernelization
- Maximum cut parameterized by crossing number
- Computing crossing numbers in quadratic time
- Parameterized analysis and crossing minimization problems
- Computing crossing numbers in quadratic time
- An ILP-based Proof System for the Crossing Number Problem
- Note on the pair-crossing number and the odd-crossing number
- Parameterised partially-predrawn crossing number
- Algorithmic complexity of finding cross-cycles in flag complexes
This page was built for publication: Crossing Numbers and Parameterized Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5452207)
