On the crossing number of complete graphs
From MaRDI portal
Publication:817025
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
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
