The convex hull of every optimal pseudolinear drawing of kn is a triangle
Article
Overview
Additional Document Info
View All
Overview
abstract
A pseudolinear (respectively, rectilinear) drawing of a graph G is optimal if it has the smallest number of crossings among all pseudolinear (respectively, rectilinear) drawings of G. We show that the convex hull of every optimal pseudolinear drawing of the complete graph Kn is a triangle. This is closely related to the recently announced result that the convex hull of every optimal rectilinear drawing of Kn is a triangle.
