Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica (ex-Scienze dell'Informazione) - D(S)I
via Salaria 113, piano terzo
Aula Seminari

Abstract:
A geometric graph is a straight-line plane drawing of a graph, possibly with intersecting edges. It is called k-locally planar if no path of length k is self-intersecting (or equivalently, the k/2 neighborhood of any vertex is intersection-free). We present a construction of such graphs with superlinear number of edges for any k. The constructed graphs have n vertices and average degree around [k/2]-times iterated log of n. Good upper bounds are missing. The order of magnitude is only known for 3-locally planar graphs: their maximum number of edges is Theta(n log n). (This is a joint result with J. Pach, R. Pinchasi, and G. Toth.)

The main tool we use is a thinning procedure that, given a edge-colored bipartite graph, produces a subgraph that avoids certain types of paths. This procedure is useful in other constructions as well: we can use it to construct an n by n 0-1 matrix with n\log\log n 1 entries avoiding the following two submatrices

11*
1*1

and

1*1
*11

For this problem n log log n is tight as shown by a matching upper bound.