Approximating the Maximum Rectilinear Crossing Number

DOI10.1007/978-3-319-42634-1_37zbMath1476.68190OpenAlexW2502983036MaRDI QIDQ2817887

Ou Liu, Matthew P. Johnson, Samuel Bald

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-42634-1_37

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (3)

Maximum rectilinear crossing number of uniform hypergraphs ⋮ Weighted Turán problems with applications ⋮ Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees

Cites Work

• Unnamed Item
• Unnamed Item
• On the obfuscation complexity of planar graphs
• The maximum of the maximum rectilinear crossing numbers of \(d\)-regular graphs of order \(n\)
• Some provably hard crossing number problems
• Which crossing number is it anyway?
• The graph crossing number and its variants: a survey
• Crossing number is hard for cubic graphs
• Thirty Essays on Geometric Graph Theory
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• Crossing Number is NP-Complete
• Complexity of Some Geometric and Topological Problems
• Maximal Rectilinear Crossing of Cycles
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• Crossing Number Problems

This page was built for publication: Approximating the Maximum Rectilinear Crossing Number