Construction of locally plane graphs with many edges

Research paper by Gábor Tardos

Indexed on: 28 Oct '11Published on: 28 Oct '11Published in: Mathematics - Combinatorics


A graph drawn in the plane with straight-line edges is called a geometric graph. If no path of length at most $k$ in a geometric graph $G$ is self-intersecting we call $G$ $k$-locally plane. The main result of this paper is a construction of $k$-locally plane graphs with a super-linear number of edges. For the proof we develop randomized thinning procedures for edge-colored bipartite (abstract) graphs that can be applied to other problems as well.