János Barát: Saturated k-plane graphs and k-planar drawings with special emphasis on k=2

We consider various topological classes of graphs. A graph G belonging to the class C is saturated if adding any edge to G results in a graph not in C. A drawing of a graph G is k-planar if any edge is intersected by at most k other edges. A graph G is k-plane if it has a k-planar drawing. Any n-vertex planar graph has at most 3n-6 edges. On the other hand, any saturated planar graph has 3n-6 edges. Any n-vertex 1-planar drawing has at most 4n-8 edges. Here the saturated graphs are dramatically different from the ones with maximum number of edges. The number of edges in saturated 1-plane graphs and 1-planar drawings can be much less than 4n. This was first noticed about a decade ago. One can prove lower and upper bounds on the minimum number of edges in n-vertex saturated 1-plane graphs or 1-planar drawings. Similar problems can be considered for k-planar drawings, where k is at least 2. However, the proof methods are rather different and there are unexpected phenomenons as k grows. In the talk, we try to review the most recent developments. We concentrate on various interesting constructions. We give an overview of a few strategies proving lower bounds. Based on joint work with Géza Tóth.