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.