Premium
Levi's Lemma, pseudolinear drawings of K n , and empty triangles
Author(s) -
Arroyo Alan,
McQuillan Dan,
Richter R. Bruce,
Salazar Gelasio
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22167
Subject(s) - lemma (botany) , mathematics , mathematical proof , combinatorics , regular polygon , graph , geometry , ecology , poaceae , biology
There are three main thrusts to this article: a new proof of Levi's Enlargement Lemma for pseudoline arrangements in the real projective plane; a new characterization of pseudolinear drawings of the complete graph; and proofs that pseudolinear and convex drawings of K n haven 2 +O ( n log n ) and O( n 2 ), respectively, empty triangles. All the arguments are elementary, algorithmic, and self‐contained.