| Topic: Schnyder Woods and Geometric Representations of Graphs (2008) | |||||||||||||
Abstract | |||||||||||||
| In the last six months I have mainly worked on problems from two different areas. I will first give an overview of my work on the number of orientations with fixed out-degrees. In contrast to this the second topic is rather concerned with structural graphs properties, namely spanning trees with many leaves. The Number of Orientations with Fixed Out-Degrees I have worked on the problems presented in this section with Stefan Felsner. A paper [8] is a available on the arXiv and a conference version [9] has been submitted. I will now outline what type of questions we consider and our main results. The concept of orientations with fixed out-degrees or α-orientations is a quite general one as we will see below. Let a graph G with vertex set V and a function α: V → N be given. An orientation X of the edges of G is an α-orientation if every vertex v has out-degree α(v). A planar map is a planar graph together with a plane drawing. Felsner [6] proves that for fixed α and M the set of α-orientations of a planar map M is a distributive lattice. This structure on the set of α-orientations found applications in drawing algorithms for example in [2], and for enumeration and random sampling of graphs in [10]. We also focus on the study of | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||