Planar Graphs and Planar Posets III

Graph Theory Seminar
Thursday, September 17, 2009 - 12:05
1 hour (actually 50 minutes)
Skiles 255
Math, GT
This is the third session in this series and  a special effort will be made to make it self contained ... to the fullest extent possible.With Felsner and Li, we proved that the dimension of the adjacency poset of a graph is bounded as a function of the genus.  For planar graphs, we have an upper bound of 8 and for outerplanar graphs, an upper bound of 5. For lower bounds, we have respectively 5 and 4.   However, for bipartite planar graphs, we have an upper bound of 4, which is best possible. The proof of this last result uses the Brightwell/Trotter work on the dimension of thevertex/edge/face poset of a planar graph, and led to the following conjecture:For each  h, there exists a constant c_h so that if P is a poset of height  h and the cover graph of P is planar, then the dimension of  P  is at most  c_h.With Stefan Felsner, we have recently resolved this conjecture in the affirmative. From below, we know from a construction of Kelly that c_h must grow linearly with  h.