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


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" [...]


  The system of instant Payday Loans Virginia allows any adult U.S. citizen. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.