Minors and planar embeddings of digraphs

Embedding graphs in surfaces is the central concept of topological graph theory. Classifying embeddability of graphs is motivated by Kuratowski’s Theorem and Robertson-Seymour theory, which confirms that the set of obstructions to embeddability in an arbitrary surface is finite. We consider embedding directed graphs in surfaces, with restrictions on the direction of arcs in the local rotation at each vertex. Clustered planar digraphs have planar embeddings in which, at each vertex, all of the in-arcs occur sequentially in the local rotation. Three different variations of minors are presented, each of which produces a finite set of obstructions to clustered planarity. These variations include new operations on digraphs, and measures which refine the partial ordering. Tournaments are digraphs with exactly one edge between every distinct pair of vertices. The domination graph of a tournament is a graph with the same vertices, and an edge between two of the vertices if every other vertex is beaten by one of those two vertices. We present two variations of domination graphs, and investigate the relationships between them and their limitations. We investigate those graphs which may be domination graphs of tournaments using excluded minors. Such graphs have a finite set of obstructions under a modification of the minor partial order.

Name thesis:degree_name

PhD

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Mathematics

Grantor dc:publisher

ResearchSpace@Auckland

Year dc:date.issued

2004

Author dc:creator

• Sneddon, Jamie David

Advisors dc:contributor.advisor

• Paul Bonnington
• Margaret Morton
• Marston Conder

Statement dc:rights

• Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Licence dc:rights.uri

• https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm

Language dc:language.iso

en

Handle dc:identifier.uri

https://hdl.handle.net/2292/441

OAI identifier oai:identifier

oai:researchspace.auckland.ac.nz:2292/441