Levi's Lemma, pseudolinear drawings of Kn, and empty triangles. Issue 4 (13th September 2017)

• Record Type: Journal Article
• Authors: Arroyo, Alan; McQuillan, Dan; Richter, R. Bruce; Salazar, Gelasio
• Is Part Of: Journal of graph theory. Volume 87:Issue 4(2018)
• Page Start: 443
• Page End: 459
• Publication Date: 2017-09-13
• Subjects: empty triangles -- Levi's Enlargement Lemma -- pseudolinear drawing -- Primary 52C30 -- Secondary 05C10 -- 68R10; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22167
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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 have n 2 + O ( n log n ) and O( n 2 ), respectively, empty triangles. All the arguments are elementary, algorithmic, and self‐contained.