Full Record

Author | Campbell, Russell J. |

Title | Finding obstructions within irreducible triangulations |

URL | http://hdl.handle.net/1828/8212 |

Publication Date | 2017 |

Date Accessioned | 2017-06-01 22:40:11 |

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 | 2020-05-17 |

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…