Open Collections

UBC Graduate Research

d-Realizers and the Minimal Graph Without One Nelson, Kristina

Abstract

We explore the work of Evans et al., who in turn have built on Schnyder’s definition of the dimension of a graph, and extended Schnyder woods to higher dimensions. Here we discuss d-realizers: sequences of d permutations on a set of vertices required to have empty intersection and d ‘suspension’ vertices. We will present a minimal graph having no d-realizer, and numerous graphs on 5, 6 and 7 vertices that do have one. Finally, we consider what possible characterization of graphs having a d-realizer could extend the triangulated-graph characterization found by Schnyder for 3 dimensional graphs.

Item Metadata

Title
d-Realizers and the Minimal Graph Without One
Creator
Nelson, Kristina
Date Issued
2014-04-19
Description
We explore the work of Evans et al., who in turn have built on Schnyder’s definition of the dimension of a graph, and extended Schnyder woods to higher dimensions. Here we discuss d-realizers: sequences of d permutations on a set of vertices required to have empty intersection and d ‘suspension’ vertices. We will present a minimal graph having no d-realizer, and numerous graphs on 5, 6 and 7 vertices that do have one. Finally, we consider what possible characterization of graphs having a d-realizer could extend the triangulated-graph characterization found by Schnyder for 3 dimensional graphs.
Subject
Graphs; Realizer; Dimension
Genre
Report
Type
Text
Language
eng
Series
University of British Columbia. CPSC 536
Date Available
2015-10-24
Provider
Vancouver : University of British Columbia Library
Rights
Attribution-NonCommercial 2.5 Canada
DOI
10.14288/1.0103600
URI
http://hdl.handle.net/2429/54896
Affiliation
Computer Science, Department of; Mathematics, Department of; Science, Faculty of
Campus
UBCV
Peer Review Status
Unreviewed
Scholarly Level
Graduate
Rights URI
http://creativecommons.org/licenses/by-nc/2.5/ca/
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial 2.5 Canada