Crossing Number of Graphs with Rotation Systems

DOI10.1007/978-3-540-77537-9_3MaRDI QIDQ5452204zbMATH 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_3

zbMATH Keywords

computational complexitycomputational geometrycrossing number

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

• Crossing numbers of graphs with rotation systems
• Mathematical Foundations of Computer Science 2004
• Crossing number is hard for cubic graphs
• Which crossing number is it anyway?
• Crossing Number is NP-Complete

Cites work

• An Extension of the String-to-String Correction Problem
• Bimodal Crossing Minimization
• Crossing number is hard for cubic graphs
• Crossing Number is NP-Complete
• Graph Drawing
• scientific article; zbMATH DE number 5763167 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3557227 (Why is no real title available?)
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 1454642 (Why is no real title available?)
• Minor-monotone crossing number
• On a cyclic string-to-string correction problem
• Removing independently even crossings

Cited in

(9)

• The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph
• The crossing number of twisted graphs
• Crossing number is hard for cubic graphs
• Crossing Number is NP-Complete
• scientific article; zbMATH DE number 5130834 (Why is no real title available?)
• scientific article; zbMATH DE number 2170413 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• Crossing numbers of graphs with rotation systems
• Unexpected behaviour of crossing sequences

This page was built for publication: Crossing Number of Graphs with Rotation Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5452204)