Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 07, 2014, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Vincent Kusters
We introduce the notion of column planarity of a subset $R$ of the vertices of a graph $G$. Informally, we say that $R$ is column planar in $G$ if we can assign $x$-coordinates to the vertices in $R$ such that any assignment of $y$-coordinates to them produces a partial embedding that can be completed to a plane straight-line drawing of $G$. Column planarity is both a relaxation and a strengthening of unlabeled level planarity. We prove near tight bounds for column planar subsets of trees: any tree on $n$ vertices contains a column planar set of size at least $14n/17$ and for any $\epsilon > 0$ and any sufficiently large $n$, there exists an $n$-vertex tree in which every column planar subset has size at most $(5/6 + \epsilon)n$.
We also consider a relaxation of simultaneous geometric embedding (SGE), which we call partial SGE (PSGE). A PSGE of two graphs $G_1$ and $G_2$ allows some of their vertices to map to two different points in the plane. We show how to use column planar subsets to construct $k$-PSGEs in which $k$ vertices are still mapped to the same point. In particular, we show that any two trees on $n$ vertices admit an $11n/17$-PSGE.
Joint work with Will Evans, Maria Saumell, and Bettina Speckmann.
Automatic MiSe System Software Version 1.4803M | admin login