Obstructions for Embedding Digraphs

We consider regular directed graphs where each vertex has indegree
and outdegree 2. Given such a digraph G, let v be a vertex that is
directly adjacent to x,y and directly adjacent from a,b. We can form
two graphs H whose order is 1 less than the order of G: delete v and
its neighbors and add either the edges ax and by or add the edges ay
and bx. In this case, we say that H is immersed in G. We extend
this immersion order by transitive closure.

We are concerned with embedding digraphs into a surface S. We
require that at each vertex the two edges directed out are not adjacent
(and hence the two edges directed in are not adjacent). For the class
of graphs described, if G embeds in S, then any immersed H also embeds
in S. So the class of graphs that embeds in S is closed under the
immersion order. Johnsan has studied these embeddings, and has proven
that there is a finite number of graphs that do not embed in S and
under the immersion order are minimal with this property. Hence these
graphs give a finite obstruction set for embedding on S.

The obstruction set for embedding on the plane is known [J]:
it consists of a triangle with six edges directed from any vertex to
any distinct vertex. The obstruction set for the projective plane is
known [DDS] one of two digraphs. DeVos (Embedding
digraphs) says that at one point they knew the obstructions for
embedding on the torus, but no longer have the list.

Problem: Find the
obstructions for directed embeddings on the torus. Find the
obstructions for directed embeddings on the Klein bottle. Other
surfaces?

References:

[J] T. Johnson, Ph.D. thesis, Princeton University

[DDS] M. DeVos, G. Ding, P.D. Seymour, On embedding digraphs in the
projective plane.

Submitted by: Dan Archdeacon, Department of Mathematics and
Statistics, University of Vermont, Burlington VT 05405 USA. (with
thanks to Matt DeVos)

Send comments to *dan.archdeacon@uvm.edu*

December 2003.