Levi's Lemma, pseudolinear drawings of , and empty triangles

DOI10.1002/JGT.22167zbMATH Open1388.52018arXiv1511.06808OpenAlexW2964030595WikidataQ124823325 ScholiaQ124823325MaRDI QIDQ4638639FDOQ4638639

Authors: Alan Arroyo, Daniel McQuillan, R. B. Richter, Gelasio Salazar 

Publication date: 27 April 2018

Published in: Journal of Graph Theory (Search for Journal in Brave)

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$(nlogn)$ and O$(n^2)$, respectively, empty triangles. All the arguments are elementary, algorithmic, and self-contained.

Full work available at URL: https://arxiv.org/abs/1511.06808

Recommendations

• Empty triangles in generalized twisted drawings of \(K_n\)
• Empty Triangles in Generalized Twisted Drawings of $K_n$
• scientific article; zbMATH DE number 5238988
• On the Levi graph of point-line configurations
• On vertex- and empty-ply proximity drawings
• Drawing \(K_{2,n}\): A lower bound
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• On the number of pseudo-triangulations of certain point sets
• scientific article; zbMATH DE number 2080112
• Greedy drawings of triangulations

zbMATH Keywords

empty trianglesLevi's enlargement lemmapseudolinear drawing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cited In (15)

• Empty triangles in good drawings of the complete graph
• Closing in on Hill's conjecture
• Complete graph drawings up to triangle mutations
• Taking a detour; or, Gioan's theorem, and pseudolinear drawings of complete graphs
• Topological drawings meet classical theorems from convex geometry
• Inserting one edge into a simple drawing is hard
• Extending drawings of graphs to arrangements of pseudolines
• Extending drawings of complete graphs into arrangements of pseudocircles
• Extending drawings of graphs to arrangements of pseudolines
• Towards crossing-free Hamiltonian cycles in simple drawings of complete graphs
• Title not available (Why is that?)
• Empty Triangles in Generalized Twisted Drawings of $K_n$
• Topological Drawings Meet Classical Theorems from Convex Geometry
• Shooting stars in simple drawings of \(K_{m,n}\)
• Convex drawings of the complete graph: topology meets geometry

This page was built for publication: Levi's Lemma, pseudolinear drawings of , and empty triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638639)