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

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

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

• 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?)
• An Extension of the String-to-String Correction Problem
• Bimodal Crossing Minimization
• Crossing Number is NP-Complete
• Crossing number is hard for cubic graphs
• Graph Drawing
• Minor-monotone crossing number
• On a cyclic string-to-string correction problem
• Removing independently even crossings

Cited in

(9)

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

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)