<?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-22T19:13:15Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/12253" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/12253</identifier><datestamp>2025-03-26T23:37:30Z</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="56ae972d-e9a2-4acb-ab97-d584b723a74b" confidence="600">Derka, Martin</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2017-08-29T14:39:13Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2017-08-29T14:39:13Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2017-08-29</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2017-08-18</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/12253</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">A string representation of a graph assigns to every vertex a curve in the plane so that two curves intersect if and only if the represented vertices are adjacent. This work investigates string representations of graphs with an emphasis on the shapes of curves and the way they intersect. We strengthen some previously known results and show that every planar graph&#xd;
has string representations where every curve consists of axis-parallel line segments with at most two bends (those are the so-called $B_2$-VPG representations) and simultaneously two curves intersect each other at most once (those are the&#xd;
so-called 1-string representations). Thus, planar graphs are $B_2$-VPG $1$-string graphs. We further show that with some restrictions on the shapes of the curves, string representations can be used to produce approximation algorithms for several hard problems. The $B_2$-VPG representations of planar graphs satisfy these restrictions. We attempt to further&#xd;
restrict the number of bends in VPG representations for subclasses of planar graphs, and investigate $B_1$-VPG&#xd;
representations. We propose new classes of string representations for planar graphs that we call ``order-preserving.&amp;apos;&amp;apos; Order-preservation is an interesting property which relates the string representation to the planar embedding of the graph, and we believe that it might prove useful when constructing string representations. Finally, we extend our investigation&#xd;
of string representations to string representations that require some curves to intersect multiple times. We show that there are outer-string graphs that require an exponential number of crossings in their outer-string representations. Our construction also proves that 1-planar graphs, i.e., graphs that are no longer planar, yet fairly close to planar graphs, may have string representations, but they are not always 1-string.</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">string representation</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">B2-VPG graph</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">string graph</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Restricted String Representations</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral 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">Doctor of Philosophy</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>