2-Regular Digraphs on Surfaces

Resource type
Thesis type
(Thesis) Ph.D.
Date created
A 2-regular digraph is one where every vertex has in-degree and out-degree 2. This thesis focuses on surface embeddings of 2-regular digraphs, one where the underlying graph is embedded in a surface and all faces are bounded by directed closed walks. Immersion acts as a natural minor-like containment relation for embedded 2-regular digraphs and this theory is linked to undirected graph minors by way of the directed medial graph. We parallel the theory of undirected graphs in surfaces by proving analogues of Whitney's Theorem and Tutte's peripheral cycles theorem for 2-regular digraphs in the sphere. Then, using a notion of branch-width and a 2-regular digraph grid theorem by Johnson, we prove that for each fixed surface S, the 2-regular digraphs embeddable in S are characterized by a finite list of immersion obstructions. We then present the current state of the art with regard to classification of obstructions for surfaces: Johnson characterized the sphere obstructions, we classify all projective plane obstructions, and we have a computer assisted partial list of obstructions for the torus and Klein bottle. We also consider two open problems in the world of undirected graphs on surfaces and resolve their analogues in the world of 2-regular digraphs on surfaces. The first conjecture by Negami we resolve in the affirmative, that a 2-regular digraph has a finite planar cover if and only if it is projective planar. The second, the strong embedding conjecture, is resolved in the negative and we provide an infinite family of well connected counter-examples.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: DeVos, Matt
Member of collection
Download file Size
etd19723.pdf 1.45 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 0