10:0010:20 
Different Tree Packing Conjectures
Anastasia Moskovaya, EPFL
Abstract:
In 1976, Gyárfás and Lehel conjectured that any
family of trees T_{1},.., T_{n} with each
T_{i} on i vertices can decompose the complete graph
on n vertices in an edgedisjoint manner. In other words, any
such family of trees packs into K_{n}. A few years
earlier, in 1967 a related conjecture was posed by Ringel. He
said that considering a tree T on n vertices, 2n−1 isomorphic
copies of it pack into K_{2n−1}. Since decades, the
way to look at this conjecture is through another conjecture,
the Graceful Tree Conjecture by Kotzig. Using a cyclical
decomposition of K_{2n−1}, the Graceful Tree
Conjecture implies Ringel’s conjecture. I will discuss these
conjectures and some of the important known results, and then
explore a new way of looking at the Graceful Tree Conjecture
through the notion of flip graphs, based on a local operation
on graceful trees. 
11:0011:20 
Partial and Constrained Level Planarity
Guido Brückner, KIT
Abstract:
Let G=(V,E) be a graph and ℓ: V → {1,...,k} a
leveling. In a levelplanar drawing of G each vertex v lies on
the horizontal line with ycoordinate ℓ(v), and edges are
drawn as noncrossing ymonotone curves.
In the problem Constrained Level Planarity (CLP), we are
further given a partial ordering ≺_{i} of
V_{i} := ℓ^{1}(i) for i ∈
{1,...,k}, and we seek a levelplanar drawing where the order
of the vertices on ℓ_{i} is a linear extension of
≺_{i}. A special case of this is Partial
Level Planarity (PLP), where we are asked to extend a given
levelplanar drawing ℋ of a subgraph H ⊆ G to a
complete drawing of G without modifying ℋ.
We give a simple algorithm with running time O(n^{5})
for CLP of singlesource graphs. We introduce a modified type
of PQtree data structure that can efficiently handle the
arising constraints to improve the running time to O(n + k l),
where l is the size of the constraints. We complement this by
showing that PLP is NPcomplete even in very restricted cases.
