Full Record

New Search | Similar Records

Author
Title Finding obstructions within irreducible triangulations
URL
Publication Date
Date Accessioned
Discipline/Department Department of Computer Science
Degree Level doctor of philosophy ph.d.
University/Publisher University of Victoria
Abstract The main results of this dissertation show evidence supporting the Successive Surface Scaffolding Conjecture. This is a new conjecture that, if true, guarantees the existence of all the wye-delta-order minimal obstructions of a surface S as subgraphs of the irreducible triangulations of the surface S with a crosscap added. A new data structure, i.e. an augmented rotation system, is presented and used to create an exponential-time algorithm for embedding graphs in any surface with a constant-time check of the change in genus when inserting an edge. A depiction is a new formal definition for representing an embedding graphically, and it is shown that more than one depiction can be given for nonplanar embeddings, and that sometimes two depictions for the same embedding can be drastically different from each other. An algorithm for finding the essential cycles of an embedding is given, and is used to confirm for the projective-plane obstructions, a theorem that shows any embedding of an obstruction must have every edge in an essential cycle. Obstructions of a general surface S that are minor-minimal and not double-wye-delta-minimal are shown to each have an embedding on the surface S with a crosscap added. Finally, open questions for further research are presented.
Subjects/Keywords graph theory; topological graph theory; obstruction; embedding algorithm; irreducible triangulation; torus; projective plane; Klein bottle
Contributors Myrvold, Wendy (supervisor)
Language en
Rights Available to the World Wide Web
Country of Publication ca
Record ID handle:1828/8212
Repository uvic
Date Retrieved
Date Indexed 2020-06-19
Issued Date 2017-06-01 00:00:00
Note [scholarlevel] Graduate;

Sample Search Hits | Sample Images | Cited Works

…7.8 7.9 7.10 7.11 7.12 7.13 7.14 7.15 7.16 7.17 7.18 7.19 7.20 7.21 7.22 7.23 7.24 7.25 7.26 A1 obstruction of N1 — Kc4 triangulation of N2 . A2 obstruction of N1 — Kh6 triangulation of N2 . B1 obstruction of N1 — Kh6 triangulation of N2 . B3…

obstruction of N1 — Kh6 triangulation of N2 . C7 obstruction of N1 — Kh4 triangulation of N2 . D9 obstruction of N1 — Kh25 triangulation of N2 D12 obstruction of N1 — Kh7 triangulation of N2 . D17 obstruction of N1 — Kh1 triangulation of N2 . E3 obstruction of…

…N1 — Kh6 triangulation of N2 . E18 obstruction of N1 — Kh2 triangulation of N2 . E22 obstruction of N1 — Kh13 triangulation of N2 C1 obstruction of N1 — Kc2 triangulation of N2 . D3 obstruction of N1 — Kh2 triangulation of N2 . D4 obstruction of N1…

…Kh19 triangulation of N2 E19 obstruction of N1 — Kc1 triangulation of N2 . F1 obstruction of N1 — Kc1 triangulation of N2 . F6 obstruction of N1 — Kc2 triangulation of N2 . G1 obstruction of N1 — Kc2 triangulation of N2 . The minor-order projective…

…plane obstruction E2 . . . viii…

…referred to as crosscaps on the nonorientable surface. For simplicity, let N0 = S0 . A topological obstruction of a surface S is a graph with neither isolated nor degree two vertices that does not embed in S, yet G − e does embed for any edge e. A minor…

obstruction has the added property that for any single edge contraction, the resulting graph embeds on S. A wye-delta obstruction is a minor obstruction with the added property that if for any degree three vertex v the resulting graph G of removing v and its…

…not hypothesize that the disconnected obstructions from the set M3 (Nk ) nor M3 (Sg ), for k = 2g, can be found as subgraphs of the irreducible triangulations to Nk+1 . For example, two disjoint copies of K5 is an obstruction to the…

.