<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T13:48:52Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/5358" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/5358</identifier><datestamp>2017-03-21T16:57:37Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="725fae34-4fc9-4c03-b152-5a9736ba5591" confidence="600">Barrera-Cruz, Fidel</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2010-08-20T19:43:38Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2010-08-20T19:43:38Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2010-08-20T19:43:38Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2010</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/5358</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The central topic of this thesis is Schnyder&amp;apos;s Theorem. Schnyder&amp;apos;s Theorem provides&#xd;
a characterization of planar graphs in terms of their poset dimension, as follows: a graph&#xd;
G is planar if and only if the dimension of the incidence poset of G is at most three. One&#xd;
of the implications of the theorem is proved by giving an explicit mapping of the vertices&#xd;
to R^2 that defines a straightline embedding of the graph. The other implication is proved&#xd;
by introducing the concept of normal labelling. Normal labellings of plane triangulations&#xd;
can be used to obtain a realizer of the incidence poset. We present an exposition of&#xd;
Schnyder’s theorem with his original proof, using normal labellings. An alternate proof&#xd;
of Schnyder’s Theorem is also presented. This alternate proof does not use normal&#xd;
labellings, instead we use some structural properties of a realizer of the incidence poset&#xd;
to deduce the result.&#xd;
Some applications and a generalization of one implication of Schnyder’s Theorem&#xd;
are also presented in this work. Normal labellings of plane triangulations can be used to&#xd;
obtain a barycentric embedding of a plane triangulation, and they also induce a partition&#xd;
of the edge set of a plane triangulation into edge disjoint trees. These two applications&#xd;
of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and&#xd;
canonical orderings to obtain a compact drawing of a graph, are also presented. A&#xd;
generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s&#xd;
Theorem was proved by Ossona de Mendez. This generalization is also presented in this&#xd;
work. The concept of order labelling is also introduced and we show some similarities of&#xd;
the order labelling and the normal labelling. Finally, we conclude this work by showing&#xd;
the source code of some implementations done in Sage.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Graph theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Simplicial complexes</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Planar graphs</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Poset dimension</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">On Schnyder&amp;apos;s Theorm</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>