Crossing Number of Graphs with Rotation Systems

DOI10.1007/978-3-540-77537-9_3zbMath1137.68501OpenAlexW1599261767MaRDI QIDQ5452204

Daniel Štefanković, Michael J. Pelsmajer, Marcus Schaefer

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 complexitycrossing numbercomputational geometry

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

Related Items (1)

Unexpected behaviour of crossing sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a cyclic string-to-string correction problem
• Crossing number is hard for cubic graphs
• Crossing Number is NP-Complete
• Removing Independently Even Crossings
• Bimodal Crossing Minimization
• An Extension of the String-to-String Correction Problem
• Graph Drawing

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