The central topic of this thesis is Schnyder's Theorem. Schnyder's Theorem provides
a characterization of planar graphs in terms of their poset dimension, as follows: a graph
G is planar if and only if the dimension of the incidence poset of G is at most three. One
of the implications of the theorem is proved by giving an explicit mapping of the vertices
to R^2 that defines a straightline embedding of the graph. The other implication is proved
by introducing the concept of normal labelling. Normal labellings of plane triangulations
can be used to obtain a realizer of the incidence poset. We present an exposition of
Schnyder’s theorem with his original proof, using normal labellings. An alternate proof
of Schnyder’s Theorem is also presented. This alternate proof does not use normal
labellings, instead we use some structural properties of a realizer of the incidence poset
to deduce the result.
Some applications and a generalization of one implication of Schnyder’s Theorem
are also presented in this work. Normal labellings of plane triangulations can be used to
obtain a barycentric embedding of a plane triangulation, and they also induce a partition
of the edge set of a plane triangulation into edge disjoint trees. These two applications
of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and
canonical orderings to obtain a compact drawing of a graph, are also presented. A
generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s
Theorem was proved by Ossona de Mendez. This generalization is also presented in this
work. The concept of order labelling is also introduced and we show some similarities of
the order labelling and the normal labelling. Finally, we conclude this work by showing
the source code of some implementations done in Sage.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5358 |
| Date | January 2010 |
| Creators | Barrera-Cruz, Fidel |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0021 seconds