**Friday, 15:15 - 15:40 h, Room: H 2038**

**Etienne de Klerk**

Improved lower bounds on crossing numbers of graphs via semidefinite programming

**Coauthor: Dmitrii V. Pasechnik**

**Abstract:**

The crossing number problem for graphs is to draw a graph in the plane with a minimum number of edge crossings. Crossing numbers are of interest for graph visualization, VLSI design, quantum dot cellular automata, RNA folding, and other applications. On the other hand, the problem is notoriously difficult. In 1973, ErdÃ¶s and Guy wrote that: "Almost all questions that one can ask about crossing numbers remain unsolved.'' For example, the crossing numbers of complete and complete bipartite graphs are still unknown in general. Moreover, even for cubic graphs, it is NP-hard to compute the crossing number.

Different types of crossing numbers may be defined by restricting drawings; thus the two-page crossing number corresponds to drawings where all vertices are drawn or a circle, and all edges either inside or outside the circle. In this talk, we will survey some recent results, where improved lower bounds were obtained for (two-page) crossing numbers of complete and complete bipartite graphs via optimization.

Talk 1 of the invited session Fri.3.H 2038

**"Algebraic symmetry in semidefinite programming"** [...]

Cluster 4

**"Conic programming"** [...]