On the crossing number of complete graphs

DOI10.1007/s00607-005-0133-3zbMath1082.05027OpenAlexW1990000829MaRDI QIDQ817025

Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser

Publication date: 2 March 2006

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-005-0133-3

zbMATH Keywords

enumerationorder types

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

On the number of plane geometric graphs ⋮ Geometric drawings of \(K_{n}\) with few crossings ⋮ Abstract order type extension and new results on the rectilinear crossing number ⋮ Convexity minimizes pseudo-triangulations ⋮ Simple realizability of complete abstract topological graphs in P ⋮ An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants ⋮ An extended lower bound on the number of(\(\leqslant k\))-edges to generalized configurations of points and the pseudolinear crossing number of \(K_n\) ⋮ Unnamed Item ⋮ 3-symmetric and 3-decomposable geometric drawings of \(K_n\) ⋮ The Complexity of Several Realizability Problems for Abstract Topological Graphs ⋮ The Crossing Number of Graphs: Theory and Computation ⋮ Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill ⋮ A lower bound for the rectilinear crossing number ⋮ On the crossing number of complete graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the crossing number of complete graphs
• Abstract order type extension and new results on the rectilinear crossing number
• A lower bound for the optimal crossing-free Hamiltonian cycle problem
• Some provably hard crossing number problems
• Which crossing number is it anyway?
• Enumerating order types for small point sets with applications
• Toward the rectilinear crossing number of \(K _{n}\): New drawings, upper bounds, and asymptotics
• \(k\)-sets, convex quadrilaterals, and the rectilinear crossing number of \(K_{n}\)
• An upper bound for the rectilinear crossing number of the complete graph
• A lower bound for the rectilinear crossing number
• Multidimensional Sorting
• Crossing Number is NP-Complete
• Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
• The Rectilinear Crossing Number of a Complete Graph and Sylvester's "Four Point Problem" of Geometric Probability
• Toward a theory of crossing numbers
• Crossing Number Problems
• On the Number of Crossings in a Complete Graph
• The rectilinear crossing number of \(K_{10}\) is 62