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.
Original language | English (US) |
---|---|
Pages (from-to) | 155-162 |
Number of pages | 8 |
Journal | Australasian Journal of Combinatorics |
Volume | 38 |
State | Published - 2007 |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics