The convex hull of every optimal pseudolinear drawing of kn is a triangle

J. Balogh, J. Leaños, S. Pan, R. B. Rlchtert, G. Salazar

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)155-162
Number of pages8
JournalAustralasian Journal of Combinatorics
Volume38
StatePublished - 2007

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'The convex hull of every optimal pseudolinear drawing of kn is a triangle'. Together they form a unique fingerprint.

Cite this