{"id":{"repo_id":"auckland-ms","oai_identifier":"oai:researchspace.auckland.ac.nz:2292/441"},"canonical_url":"https://search.dev.ndltd.org/etd/auckland-ms/oai:researchspace.auckland.ac.nz:2292/441","repository":{"repo_id":"auckland-ms","name":"University of Auckland","base_url":"https://researchspace.auckland.ac.nz/server/oai/request"},"display":{"title":"Minors and planar embeddings of digraphs","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Sneddon, Jamie David"],"institution":"ResearchSpace@Auckland","degree_name":"PhD","degree_level":"Doctoral","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":["Paul Bonnington","Margaret Morton","Marston Conder"],"committee_chairs":[],"committee_members":[],"year":2004,"date_issued":"2004","date_published":"2004","updated_at":"2026-07-24T01:02:40Z","subjects":[],"languages":["en"],"rights":["Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated."],"rights_urls":["https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2292/441","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Paul Bonnington","Margaret Morton","Marston Conder"]},{"key":"dc:creator","label":"Author","values":["Sneddon, Jamie David"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2007-05-24T22:58:07Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2007-05-24T22:58:07Z"]},{"key":"dc:date.issued","label":"Date","values":["2004"]},{"key":"dc:publisher","label":"Institution","values":["ResearchSpace@Auckland"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["UoA1207305"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["PhD"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["The University of Auckland"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated."]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2292/441"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["Scanned from print thesis"]},{"key":"dc:title","label":"Title","values":["Minors and planar embeddings of digraphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Paul Bonnington","Margaret Morton","Marston Conder"],"dc:creator":["Sneddon, Jamie David"],"dc:date.accessioned":["2007-05-24T22:58:07Z"],"dc:date.available":["2007-05-24T22:58:07Z"],"dc:date.issued":["2004"],"dc:description.abstract":["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."],"dc:format":["Scanned from print thesis"],"dc:identifier.uri":["https://hdl.handle.net/2292/441"],"dc:language.iso":["en"],"dc:publisher":["ResearchSpace@Auckland"],"dc:relation.isreferencedby":["UoA1207305"],"dc:rights":["Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated."],"dc:rights.uri":["https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm"],"dc:title":["Minors and planar embeddings of digraphs"],"dc:type":["Thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["PhD"],"thesis:institution_name":["The University of Auckland"]},"updated_at":"2026-07-24T01:02:40Z"}