 |
Abstract: In 1989, Walter Schnyder proved that a graph is planar if and only if the dimension of its incidence poset is at most 3. The proof requires the development of a fascinating sequence of structural results for planar graphs beginning with the concept of a normal labelling. Schnyder's original motivation was the following important (real world) layout problem: Given a planar graph on n vertices, find a small rectangular grid on which the graph admits a non-crossing drawing using straight lines for edges with all vertices located at (integer) grid points. Schnyder's theorem has been extended by several researchers. For example, Brightwell and Trotter showed that the poset of vertices, edges and faces of a convex polytope in R^3 has dimension 4 and that the removal of any vertex or any face lowers it to 3. Recently, de Mendez showed that the family of all normal labellings of a planar triangulation forms a distributive lattice, and the algebraic properties this result implies have focused attention on other structural properties of planar graphs.
This talk should be accessible to undergraduates who have had a course in combinatorics or graph theory. I'll try to include nuggets of material which should be of special interest to grad students and faculty without compromising accessibility to a larger audience.
This talk will be accessible to undergraduates.
|