Graph theory seminar - Fidel Barrera Cruz

Given a graph G = (V,E) we define its incidence poset P = (V ∪ E,<G) where x <G y if and only if x ∈ V , y ∈ E and x is an endpoint of y. W. Schnyder provided a characterization of planar graphs in terms of the dimension of their incidence poset. In his proof, Schnyder developed several concepts, such as normal labellings, dual orders and tree decompositions, which are by themselves very useful in the context of planar graphs. The main purpose of this talk is to present a short and direct proof of Schnyder’s result.