Crossing Numbers and Parameterized Complexity

DOI10.1007/978-3-540-77537-9_6MaRDI QIDQ5452207zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) 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)

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

Cites work

• Computing crossing numbers in quadratic time
• Decidability of string graphs
• Graph Drawing
• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 5763167 (Why is no real title available?)
• scientific article; zbMATH DE number 5019924 (Why is no real title available?)
• Note on the pair-crossing number and the odd-crossing number
• String graphs requiring exponential representations
• Which crossing number is it anyway?

Cited in

(18)

• Some provably hard crossing number problems
• Which crossing number is it anyway?
• Computing crossing numbers in quadratic time
• Parameterized analysis and crossing minimization problems
• Exact crossing number parameterized by vertex cover
• Algorithmic complexity of finding cross-cycles in flag complexes
• On the Pseudolinear Crossing Number
• Crossing number is hard for kernelization
• An ILP-based Proof System for the Crossing Number Problem
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Maximum cut parameterized by crossing number
• Computing crossing numbers in quadratic time
• Graph Drawing
• Parameterised partially-predrawn crossing number
• Parameterized algorithms for beyond-planar crossing numbers
• Crossing number is NP-hard for constant path-width (and tree-width)
• A unified FPT framework for crossing number problems
• Note on the pair-crossing number and the odd-crossing number

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)