Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, February 20, 2007, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Florian Zickfeld (TU Berlin)
Orientations of planar maps (that is planar graphs with fixed embeddings) with out-degrees given by a function α are called α-orientations. The concept of an α-orientation provides a unified approach to many structures such as Eulerian orientations, bipartite f-factors, Schnyder woods and bipolar orientations. For a given class of planar maps and out-degree functions we study the maximum number of α-orientations that can occur.
I explain how the number of α-orientations on a planar map with n vertices can be bounded from above by 3.73^n and introduce a family of plane graphs with 2.598^n α-orientations. I also present specialized bounds for the above mentioned structures. I then discuss a reduction to counting bipartite perfect matchings and known facts about the complexity of counting α-orientations. I conclude by posing some open problems.
Joint work with Stefan Felsner.
Automatic MiSe System Software Version 1.4803M | admin login