Straight-Ahead Cycles in Drawings of Eulerian Graphs



Consider a drawing of an Eulerian graph in the plane (in a drawing non-adjacent edges are allowed to cross once transversely). We can partition the edges into straight-ahead walks by always leaving a vertex on the edge opposite in the local rotation from the one we enter, that is, so that there are the same number of edges on the left and the right as we pass through a vertex. Note that these opposite edges exist exactly when the vertex is of even degree, hence the Eulerian condition.

Question: Does every Eulerian graph have a drawing with a straight-ahead Eulerian cycle?

I have [HH] such drawings for every odd-order complete graph. The answer is yes [S] for all 8 Eulerian graphs on 6 vertices, all 37 Eulerian graphs on 7 vertices, and all 184 Eulerian graphs on 8 vertices. The answer is yes [H] for all Eulerian complete bipartite graphs.

We also ask for the opposite extreme in drawings of the complete graph.

Question [HH]: Does every K_n for n = 6t+1 or n = 6t+3 have a drawing such that every straight-ahead cycle is a triangle?

The congruence conditions on n ensure that the graph is Eulerian and that the number of edges is divisible by three. I can find such a drawing of K_7 but not of K_9. The corresponding question for bipartite graphs would be to demonstrate a drawing of K_{2r,2s} with all straight-ahead cycles quadrilaterals. These are given in [H].

References:

[H] H. Harborth, Eulerian straight ahead cycles in drawings of complete bipartite graphs, manuscript.

[HH] H. Harborth, M. Harborth, Straight ahead cycles in drawings of complete graphs, Rostock Math. Kolloq. 38 (1989) 71-75.

[S] K. Scheel-Bielefeld, Geradeausdarstellungen von Eulershen Graphen, Diplom thesis, Tech. Univ. Braunschweig.


Submitted by: Heiko Harborth, Diskrete Mathematik, Technische Universitat Braunschweig, Pockelsstrasse 14, D-38106 Braunschweig, Germany [Some additional editing and facts were supplied by Dan Archdeacon.]

Send comments to dan.archdeacon@uvm.edu and to h.harborth@tu-bs.de