<?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-22T17:22:50Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1090" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1090</identifier><datestamp>2017-03-21T19:54:20Z</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="author" lang="en" authority="9bbc1b41-596c-46e5-b826-f436ea393f0e" confidence="600">Chan, Hubert</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:25:39Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:25:39Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2003</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2003</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1090</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">We can visualize a graph by producing a geometric representation of the        graph in which each node is represented by a single point on the plane,        and each edge is represented by a curve that connects its two        endpoints.       
    Directed graphs are often used to model hierarchical structures; in        order to visualize the hierarchy represented by such a graph, it is        desirable that a drawing of the graph reflects this hierarchy.    This can        be achieved by drawing all the edges in the graph such that they all        point in an upwards direction.    A graph that has a drawing in which all        edges point in an upwards direction and in which no edges cross is known        as an upward planar graph.    Unfortunately, testing if a graph is upward        planar is NP-complete.       
    Parameterized complexity is a technique used to find efficient        algorithms for hard problems, and in particular, NP-complete problems.          The main idea is that the complexity of an algorithm can be constrained,        for the most part, to a parameter that describes some aspect of the        problem.    If the parameter is fixed, the algorithm will run in polynomial        time.       
    In this thesis, we investigate contracting an edge in an upward planar        graph that has a specified embedding, and show that we can determine        whether or not the resulting embedding is upward planar given the        orientation of the clockwise and counterclockwise neighbours of the given        edge.    Using this result, we then show that under certain conditions, we        can join two upward planar graphs at a vertex and obtain a new upward        planar graph.    These two results expand on work done by Hutton and        Lubiw.       
    Finally, we show that a biconnected graph has at most &amp;lt;i&amp;gt;k&amp;lt;/i&amp;gt;!8&amp;lt;sup&amp;gt;&amp;lt;i&amp;gt;k&amp;lt;/i&amp;gt;-1&amp;lt;/sup&amp;gt; planar        embeddings, where &amp;lt;i&amp;gt;k&amp;lt;/i&amp;gt; is the number of triconnected components.    By using        an algorithm by Bertolazzi et al.   that        tests whether a given embedding is upward planar, we obtain a        parameterized algorithm, where the parameter is the number of        triconnected components, for testing the upward planarity of a        biconnected graph.    This algorithm runs in &amp;lt;i&amp;gt;O&amp;lt;/i&amp;gt;(&amp;lt;i&amp;gt;k&amp;lt;/i&amp;gt;!8&amp;lt;sup&amp;gt;&amp;lt;i&amp;gt;k&amp;lt;/i&amp;gt;&amp;lt;/sup&amp;gt;&amp;lt;i&amp;gt;n&amp;lt;/i&amp;gt;&amp;lt;sup&amp;gt;3&amp;lt;/sup&amp;gt;) time.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">575170 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</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="rights" lang="en">Copyright: 2003, 
  Chan, Hubert. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">graph theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">graph drawing</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">parameterized complexity</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">upward planarity</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs</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">School of Computer Science</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>