Informatisches Kolloquium SoSe 2014
When: Monday, 23.06.2014 – 17:15
Recent Advances in Crossing Minimization
The crossing number problem asks for the minimum number of edge crossings that can be achieved by drawing a given graph in the 2-dimensional plane. It has originally been stated by Turan during the second world war and published in 1954. Since then, many interesting theoretical and practical results have been obtained. We will survey some of the more recent results. Despite the many published papers on this problem and its variants, the crossing number is only known for very few graph classes. Although the Harary-Hill conjecture provides a closed formula for the crossing number of complete graphs, it has only been settled for graphs with up to 12 vertices. We will review recent results and present further progress concerning the crossing number of complete graphs. We will discuss why many experts think that the new approaches will have the strength to settle this open problem. For general graphs, we will present approaches based on integer linear programming formulations for computing the exact crossing number. Our branch-and-cut algorithms are able to compute the exact crossing numbers for general sparse graphs with up to 100 vertices and crossing number up to 37 within 30 minutes. We will also survey recent approximation results for the crossing number. For general graphs, no polynomial time algorithm is known approximating the crossing number within some non-trivial factor. However, for certain graph classes like “almost planar graphs” of bounded degree, the crossing number can be approximated by a constant factor.
Professor Dr. Petra Mutzel has studied Mathematics at Universität Augsburg. After her Ph.D. in Computer Science, which she received 1994 at the Universität zu Köln, she was member of the Max-Planck-Institut für Informatik in Saarbrücken, where she also got her habilitation in 1999. After a temporary professorship at the Universität Heidelberg, she got a full professorship for Algorithms and Data Structures at the Technische Universität Wien. Since 2004, she is full professor for Algorithm Engineering at the Technische Universität Dortmund. She is Associate Editor of the Journal of Graph Algorithms and Applications (JGAA), Mathematical Programming Computation (MPC), the EURO Journal on Computational Optimization, the Graph Drawing E-print Archive, and the ACM Journal on Experimental Algorithmics. In the year 2000, she got the research prize “Technische Kommunikation 2000” by the Alcatel SEL Stiftung für Kommunikationsforschung. Her research focuses on combinatorial optimization problems as well as on graph data structures and algorithms with the main application areas graph drawing, network design, and cheminformatics.
Prof. Ulrike von Luxburg, ML