03.02.2016

Informatik-Kolloquium

Im Wintersemester 2015/2016 findet im Rahmen des Informatik-Kolloquiums der folgende Vortrag statt:

Mittwoch, 3. Februar 2016, 16.15 Uhr, Übungsraum II

Dr. Alex Ravsky, Pidstryhach Institute for Applied Problems of Mechanics and Mathematics, National Academy of Sciences of Ukraine, Lviv

On collinear sets in straight line drawings

We consider straight line drawings of planar graphs with possible edge crossings. The untangling problem is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let fix(G) denote the maximum number of vertices of a planar graph G that can be left fixed in the worst case, over all drawings of G. In the allocation problem, we are given a planar graph G on n vertices together with an n-point set X in the plane. The aim is to draw G without edge crossings so that as many vertices as possible are located in X. Let fit(G) denote the maximum number of vertices fitting this purpose in the worst case, over all point sets with n points. As fix(G) ≤ fit(G), we are interested in lower bounds for fix(G) and in upper bounds for fit(G).

For any ε>0, we construct an infinite sequence of graphs with fit(G)=O(n^{σ+ε}), where σ<0.99 is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first known family of graphs with fit(G)=o(n). On the other hand, we prove that fix(G) ≥ sqrt{n/30} for any graph G with treewidth at most 2. This extends a known lower bound for outerplanar graphs. In both proofs, collinear sets of vertices play an important role.

This is joint work with Oleg Verbitsky (HU Berlin).
The full paper is available at http://arxiv.org/abs/0806.0253
The untangling problem is the base of the popular online game “Planarity” (http://planarity.net)