MiniSymposium on Combinatorial Algorithms

Abstract:
In 1976, Gyárfás and Lehel conjectured that any family of trees T₁,.., T_n with each T_i on i vertices can decompose the complete graph on n vertices in an edge-disjoint 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.

Abstract:
A unique sink orientation (USO) is an orientation of the n-dimensional hypercube such that every nonempty face has a unique sink. The main algorithmic problem is to find the global sink of the USO. In this talk, I present a simple randomized algorithm to find the global sink of the USO.

Abstract:
Let G=(V,E) be a graph and ℓ: V → {1,...,k} a leveling. In a level-planar drawing of G each vertex v lies on the horizontal line with y-coordinate ℓ(v), and edges are drawn as non-crossing y-monotone 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 level-planar 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 level-planar drawing ℋ of a subgraph H ⊆ G to a complete drawing of G without modifying ℋ. We give a simple algorithm with running time O(n⁵) for CLP of single-source graphs. We introduce a modified type of PQ-tree 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 NP-complete even in very restricted cases.

Abstract:
Given a set of points in the plane, one can always find three concurrent lines such that they divide the set into six equal parts. This theorem was proved by a topological argument originally. I will present a similar but algorithmic proof. My algorithm runs in O(n²log(n)) time.