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.