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


  In particular, Payday Loans Texas can cater to the needs of its residents. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.