<?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-22T10:04:18Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/10652" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/10652</identifier><datestamp>2025-03-26T23:36:13Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</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="advisor">Biedl, Therese</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="ddb2c8aa-5177-4306-a2c1-ecf355a1eab5" confidence="600">Demontigny, Philippe</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2016-08-18T15:14:32Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2016-08-18T15:14:32Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2016-08-18</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2016-08-11</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/10652</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In this thesis, we study drawings of maximal outerplanar graphs that place vertices on integer coordinates. We introduce a new class of graphs, called umbrellas, and a new method of splitting maximal outerplanar graphs into systems of umbrellas. By doing so, we generate a new graph parameter, called the umbrella depth (ud), that can be used to approximate the optimal height of a drawing of a maximal outerplanar graph. We show that for any maximal outerplanar graph G, we can create a flat visibility representation of G with height at most 2ud(G) + 1. This drawing can be transformed into a straight-line drawing of the same height. We then prove that the height of any drawing of G is at least ud(G) + 1, which makes our result a 2-approximation for the optimal height. The best previously known approximation algorithm gave a 4-approximation. In addition, we provide an algorithm for finding the umbrella depth of G in linear time. Lastly, we compare the umbrella depth to other graph parameters such as the pathwidth and the rooted pathwidth, which have been used in the past for outerplanar graph drawing algorithms.</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">Approximation Algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Outerplanar Graph</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Layered Drawing</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Umbrella</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Umbrella System</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Umbrella Depth</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Height</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Flat Visibility Representation</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Biedl, Therese</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</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>