Crossing Numbers of K_n for Geometric and Topological Drawings

-- Oswin Aichholzer (TU Graz)

Time: 14:00 -- Location: https://bbb.lri.fr/b/jer-k22-eqk

In the area of crossing numbers we ask for minimizing the number of edge intersections in a drawing of a graph. There is a rich variety of crossing number problems: Which graphs do we consider, what exactly is a drawing of a graph and on which surface is it drawn, and how are intersections counted? In this talk we will concentrate on the crossing number of complete graphs drawn in the plane, including their rich history around Hill's conjecture.

We will have a look at geometric drawings (vertices are points in the plane and edges of the graph are straight line segments), and simple drawings (edges are simple Jordan arcs with at most one pairwise intersection), which are also called simple topological graphs. Our results ar based on a representation of the complete graph with order types (for geometric graphs) and rotation systems (for simple drawings). We will presen recent developements, as well as (old and new) open questions.

Category: seminars
Tags: Combi seminar combinatorics