2025/01/09 by I.L. Chen, Chen, Isaac, Oriol Solé-Pi +1 · 1 citation
Computer Science · Engineering · #05C10 #3D Shape Modeling and Analysis #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2501.04980
openalex publication_date 2025/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the crossing profile of a drawing of a graph. This is a sequence of integers whose (k+1)th entry counts the number of edges in the drawing which are involved in exactly k crossings. The first and second entries of this sequence (which count uncrossed edges and edges with one crossing, respectively) have been studied by multiple authors. However, to the best of our knowledge, we are the first to consider the entire sequence. Most of our results concern crossing profiles of rectilinear drawings of the complete graph Kn. We show that for any k≤ (n-2)2/4 there is such a drawing for which the kth entry of the crossing profile is of magnitude Ω(n). On the other hand, we prove that for any k ≥ 1 and any sufficiently large n, the kth entry can also be made to be 0. As our main result, we essentially characterize the asymptotic behavior of both the maximum and minimum values that the sum of the first k entries of the crossing profile might achieve. Our proofs are elementary and rely mostly on geometric constructions and classical results from discrete geometry and geometric graph theory.