0xDE ([info]11011110) wrote,
@ 2008-11-25 09:00:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
Entry tags:graph drawing, nauru graph, tools

Yet another drawing of the Nauru graph
I've previously posted about drawing this graph, the unique 3-regular 24-vertex symmetric graph, here, here, and here.

Today a co-author pointed me towards tikz, a package for drawing things in TeX. And what do I find as the most recently posted example? The same graph, drawn in yet another way. They call it the "star graph", but (1) that's the name for the infinite family of Cayley graphs of Sn to which it belongs, and (2) it's a bad name because a star is also a tree with one non-leaf node; the Cayley graphs have as generators a set of swaps forming a star tree. Anyway, their drawing is pretty close to my drawing of it as a hexagonal torus tiled with smaller hexagons, but with the wraparound torus edges drawn across the planar part. For comparison, here are the tikz image (hotlinked) and my image:

Nauru graph as hexagons crossed by wraparound edges

Nauru graph on a hexagonal torus


(3 comments) - (Post a new comment)

Another Interpretation (may be obvious)
(Anonymous)
2008-11-25 08:34 pm UTC (link)
This 24 vertex graph can also be thought of as a pancake graph (edges are formed by flipping the top 2,3,4 elements). Another related graph is the Bubble Sort Graph (Shown in the book by Prof. Knuth, GraphBase - Page 35) which is also a 24 vertex 3 regular graph (it is a truncated octahedron).

(Reply to this) (Thread)

Re: Another Interpretation (may be obvious)
(Anonymous)
2008-11-25 08:42 pm UTC (link)
Take back - in is not a pancake graph

(Reply to this) (Parent)

Re: Another Interpretation (may be obvious)
[info]11011110
2008-11-25 09:32 pm UTC (link)
The "bubble sort graph" is more commonly called a permutohedron but that's a pretty good name for it: colorful and an accurate description of the set of transpositions that generate it.

(Reply to this) (Parent)


(3 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…