<?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:12:59Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/6750" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/6750</identifier><datestamp>2017-03-21T15:11:22Z</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="69c3a7b0-ba9f-4325-bdd6-fee0a130af1e" confidence="600">Hosseini Alamdari, Soroush</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2012-05-18T21:49:38Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2012-05-18T21:49:38Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2012-05-18T21:49:38Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2012</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/6750</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">A straight line drawing of a graph is an open weak rectangle-of-influence&#xd;
(RI) drawing, if there is no vertex in the relative interior of the axis&#xd;
parallel rectangle induced by the end points of each edge.&#xd;
Despite recent interest of the graph drawing community in rectangle-of-influence drawings, no algorithm is known to test whether a&#xd;
graph has a planar open weak RI-drawing, not even for inner triangulated&#xd;
graphs.&#xd;
&#xd;
In this thesis, we have two major contributions. First we study open weak RI-drawings of plane graphs that must have a non-aligned frame, i.e., the graph obtained from&#xd;
removing the interior of every filled triangle is drawn such that no two&#xd;
vertices have the same coordinate. We introduce a new way to assign labels to angles, i.e., instances of vertices on faces. Using this labeling, we provide necessary and sufficient conditions characterizing those plane graphs that have open weak RI-drawings with non-aligned frame. We also give a polynomial algorithm to construct  such a drawing if one exists.&#xd;
&#xd;
Our second major result is a negative result: deciding if a planar graph (i.e., one where we can choose the planar embedding) has an open weak RI-drawing is NP-complete. NP-completeness holds even for open weak RI-drawings with non-aligned frames.</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">Computational Geometry</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Graph Drawing</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Planar Open Rectangle-of-Influence Drawings</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>