DeBruijin Diagrams/Shift Register Graphs

Date: 10/30/2001 at 12:53:05
From: Anthony Di Bona
Subject: Graphing Theory - DeBruijin Diagrams/Shift Register Graphs

We are currently studying de Bruijin diagrams and shift register 
sequences. I've been able to draw some simple examples e.g. D(2,4) 
for 'p' letters = 2 and words of length 'n' = 4.  I just know there 
must be a general layout to these things to make them more elegant 
looking.  

My specific problem is how to graph D(3,3) and then come up with a 
shift register sequence from that graph. I know the idea is to connect 
an arc from word b1b2...bn-1 to every word of the form b2b3...bn.  
With 27 arcs coming off 9 vertices, things get out of hand fairly 
quickly. Is there a shape I should be aiming for?

Date: 10/31/2001 at 03:14:28
From: Doctor Pete
Subject: Re: Graphing Theory - DeBruijin Diagrams/Shift Register 
Graphs

Hi,

I assume that the problem here is not really about the structure of 
the graph, but rather how to draw the graph in a way that reveals its 
structure more clearly. The other part of the question, i.e., finding 
a de Bruijn sequence from the graph, is not too hard because there are 
many to choose from, and all it amounts to is finding an Eulerian 
circuit on the corresponding digraph.

That said, the particular way I want you to arrange the nine vertices

     {00, 01, 02, 10, 11, 12, 20, 21, 22}

is to imagine them on the Cartesian plane with the following 
coordinates:

     00:  (0,0)
     11:  (0,2)
     22:  (0,-2)
     10:  (1,1)
     21:  (1,0)
     02:  (1,-1)
     01:  (-1,1)
     12:  (-1,0)
     20:  (-1,-1).

There is a certain logic to this arrangement, because we can now 
easily draw the following directed edges, which are straight lines:

     001:  (0,0) -> (-1,1)
     002:  (0,0) -> (1,-1)
     100:  (1,1) -> (0,0)
     200:  (-1,-1) -> (0,0),

     010:  (-1,1) -> (1,1)
     101:  (1,1) -> (-1,1)
     202:  (-1,-1) -> (1,-1)
     020:  (1,-1) -> (-1,-1),

and so forth, the other segments being 012, 120, 021, 210, 110, 011, 
220, 022. These are pretty obvious. The next ones are also straight 
line segments, but they cross over the previously drawn edges: 122, 
221, 211, 112. The next 4 edges are curved, but are not difficult to 
draw in a systematic/symmetrical way:

     121, 212, 102, 201.

The remaining 3 edges are the loops: 000, 111, 222.  You may verify 
that we have enumerated all 3^3 edges. You may also verify that each 
vertex, as drawn, has in-degree 3 and out-degree 3.

I'd say this is about the clearest way to draw this particular graph.  
From here it is not difficult to find an Eulerian circuit by trial and 
error.  This I leave up to you.

- Doctor Pete, The Math Forum
  http://mathforum.org/dr.math/