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

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)

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

• 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?)
• Computing crossing numbers in quadratic time
• Decidability of string graphs
• Graph Drawing
• Note on the pair-crossing number and the odd-crossing number
• String graphs requiring exponential representations
• Which crossing number is it anyway?

Cited in

(15)

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

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)