The 2nd-convex hull of every optimal rectilinear drawing of K_n is a triangle

2014/11/02 by Leaños, J., Lomeli, M., Ramírez-Ibáñez, M. +1
#05C10 #68R10 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1411.1699

Abstract

A rectilinear drawing of a graph G is optimal if it has the smallest number of crossings among all rectilinear drawings of G. In this paper it is shown that for n≥ 8, the second convex hull of every optimal rectilinear drawing of the complete graph K_n is a triangle.

Related

• Faces in rectilinear drawings of complete graphs
• On the 2-colored crossing number
• Optimal Morphs of Convex Drawings
• Computational search of small point sets with small rectilinear crossing number
• Greedy Rectilinear Drawings