NB: A PDF version of this announcement (suitable for posting) is also available.

Orientations of Planar Graphs

Stefan Felsner

Thursday, Sept. 25, 2008
007 Kemeny Hall, 4 pm
Tea 3:30 pm, 300 Kemeny Hall

Abstract: We consider orientations of planar graphs, e.g., bipolar orientations, Schnyder woods and general alpha-orientations. To motivate their study we show some applications of these objects. Then we turn to counting problems and ask questions like: How many bipolar orientations can a planar graph on n vertices have? How many Schnyder woods of triangulations with n vertices exist? Regarding the first question we can only provide bounds but in the second case there is a closed formula and a bijective proof. If time allows we introduce a distributive lattice structure on alpha-orientations and explain some generalizations.

This talk will be accessible to graduate students.