Felix Herter

On the Size of Simultaneous Geometric Embeddings for a Tree and a Matching

Betreuer: Klaus Kriegel
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 11.02.2014

Kurzbeschreibung

Given k planar graphs on a shared vertex set V , simultaneous geometric embedding (SGE) is the problem of finding an embedding of V into the plane such that none of the k graphs intersects itself when edges are drawn as straight line segments. Several positive results, i.e., graphs that always admit an SGE, as well as negative results are known today.

In this thesis, we analyse the size of drawings obtained by two algorithms from Cabello et al. [1]. The first creates an SGE for a wheel and a cycle. We show that an O(n^2) x O(n^2) integer grid suffices to support the resulting drawing. The second creates an SGE for a tree and a matching.

Here, we show that there exist graphs such that a grid with more than singly exponential size is needed if one uses the original algorithm. Afterwards an improvement is suggested so that singly exponential size suffices. Furthermore, we prove that a wheel and the union of two matchings always admit an SGE. In contrast to that, we give two wheels on the same six vertices such that each planar embedding of one forces the other into intersecting itself.