<?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-22T15:14:56Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/5174" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/5174</identifier><datestamp>2017-03-21T17:22:01Z</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" authority="444a442c-c8e3-4381-93b5-a755f8f3e0ef" confidence="600">Gordon, Taylor</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2010-05-18T18:11:24Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2010-05-18T18:11:24Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2010-05-18T18:11:24Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2010-05-13</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/5174</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">We discuss the problem of embedding planar graphs onto the plane with pre-specified vertex locations. In particular, we introduce a method for constructing such an embedding for both the case where the mapping from the vertices onto the vertex locations is fixed and the case where this mapping can be chosen. Moreover, the technique we present is sufficiently abstract to generalize to a method for constructing simultaneous planar embeddings with fixed vertex locations. In all cases, we are concerned with minimizing the number of bends per edge in the embeddings we produce.&#xd;
&#xd;
In the case where the mapping is fixed, our technique guarantees embeddings with at most 8n - 7 bends per edge in the worst case and, on average, at most 16/3n - 1 bends per edge. This result improves previously known techniques by a significant constant factor.&#xd;
When the mapping is not pre-specified, our technique guarantees embeddings with at most O(n^(1 - 2^(1-k))) bends per edge in the worst case and, on average, at most O(n^(1 - 1/k)) bends per edge, where k is the number of graphs in the simultaneous embedding. This improves upon the previously known O(n) bound on the number of bends per edge for k at least 2. Moreover, we give an average-case lower bound on the number of bends that has similar asymptotic behaviour to our upper bound.</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 Drawing</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Simultaneous Embeddings</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Graph Theory</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Simultaneously Embedding Planar Graphs at Fixed Vertex Locations</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>