Back to search

University of Waterloo

Restricted String Representations

Abstract

dc:description.abstract

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 has string representations where every curve consists of axis-parallel line segments with at most two bends (those are the so-called B2-VPG representations) and simultaneously two curves intersect each other at most once (those are the so-called 1-string representations). Thus, planar graphs are B2-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 B2-VPG representations of planar graphs satisfy these restrictions. We attempt to further restrict the number of bends in VPG representations for subclasses of planar graphs, and investigate B1-VPG representations. We propose new classes of string representations for planar graphs that we call ``order-preserving.'' 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 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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Derka, Martin
Advisor dc:contributor.advisor
  • Biedl, Therese

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/12253

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Derka, Martin. Restricted String Representations. University of Waterloo, 2017. http://hdl.handle.net/10012/12253