General Petersen Graphs in OpenSCAD

The field of graph theory is diverse and interesting. There are many topics to explore and endless different representations of different graphs. A particularly interesting side of graph theory to explore involves different embeddings of graphs in 3 Space. This is exciting in part due to the modern ability to 3D print. Given that there are so many different ways to embed the same graph, one has reason to be interested in spatial embeddings of graphs that illustrate the unique and interesting properties of a graph. Considering the question of which embedding to choose is putting the cart before the horse however, as there is a more pressing question to consider: How do we represent spatial embeddings of graphs at all?

Towards answering that question, I have been learning to use OpenSCAD in order to model graphs. A class of graphs I find interesting are the Generalized Petersen graphs.  A Generalized Petersen graph, GP(n, k) has 2n labelled vertices with labels 0, 1, … , n-1, 0′, 1′, … , (n-1)’ and edges of the form (i, i’), (i, i+1), and (i’, (i + k)’) where all numbers are read mod n. The edges (i, i+1) form the “outer” rim of the graph, the edges (i’, (i+k)’) form the “inner” rim of the graph, and the edges (i, i’) form the “spokes” of the graph. It has been shown that all Generalized Petersen graphs have a Tait coloring. A Tait coloring of a trivalent graph (each vertex has three edges attached or valence 3) is an edge coloring in three colors of the graph where each vertex is adjacent to all three colors. I decided to try and realize an a Tait colored embedding of GP(11, 3) in OpenSCAD.

Learning to use OpenSCAD has been an adventure in realizing that all the coding tips and tricks I’ve picked up still apply. At first, I approached the problem of drawing GP(11, 3) by hard coding every edge. After realizing that that was tiring and a pain, I started using loops to draw the outer rim and the spokes of the graph. I wrote loops that drew the outer rim and the spokes of GP(11, 3). The loops worked by drawing an edge between vertex 0, (1, 0, 0), and vertex 0 rotated by 360/11 degrees (vertex 1) as well as between vertex 0 and vertex 0′, (1, 0, dist(vertex 0, vertex 1)) then drawing an edge between vertex 1 and vertex 1 rotated by 360/11 degrees (vertex 2) as well as between vertex 1 and vertex 1′, etc. From there I realized that not only could I condense the two loops I had written but that I could draw the inner rim in the same loop as well. Note that this embedding draws the outer rim as a polygon approximating a circle. This picture of a crown was my first attempt at drawing both rims and the spokes of the graph in the same loop. The Crown

This picture illustrates the outer rim but not the spokes or the inner rim. I had used the wrong points in the OpenSCAD code trying to create the spokes and inner rim which had connected the spokes to two vertices on the outer rim instead of across the graph to create the inner rim. This obviously does not follow the correct form for a Generalized Petersen graph, but it did result in a pretty circlet that could be colored and printed.

After inadvertently making the crown, I starting thinking about how I could draw the inner rim in for any valid k given instead of hard coding GP(11, 3). I also realized that I could easily change my current code to correctly draw the outer rim and spokes for any given value of n by rotating by 360/n degrees instead of 360/11 degrees. In order to draw the inner rim, I chose to use a similar method to the one I used to draw the outer rim and spokes . To draw the inner rim, vertices i’ and (i+k)’ have to have an edge. In order to draw this in using the same loop, I drew an edge between vertex 0′ and vertex 0′ rotated by k*360/n degrees (vertex (0+k)’) and repeated that process the same way as before. This created a properly drawn embedding of GP(n, k) given valid parameters. I decided that aesthetically having the i and i’ vertices be aligned vertically was not pleasant to look at, so I modified that code so that the “lower” (outer) rim could be scaled. Doing so resulted in the following picture of a peanut butter cup (GP(11, 3)).Peanut Butter Cup

Looking at this peanut butter cup was much more pleasant and also illustrative of a fun geometric property of GP(11, 3). When looking at the structure from the top, the outer rim almost disappears as its shape is created by the intersections of the inner rim. After all that, you might notice that this graph is only one color. That is due to the fact that a Tait coloring of this graph cannot be easily drawn using the loop that I have written. The current loop essentially draws a 3 edge chunk n times, each time rotated by 360/n degrees. Since simply coloring each edge a different color and rotating that does not result in a valid coloring, several logic statements are needed to actually realize a Tait coloring on this graph. This code can currently draw any GP(n, k). I am not sure that a Tait coloring on any distinct GP(n, k)  can be drawn in the same way.

For most of the embeddings I work with this semester, I am using a simple module in OpenSCAD called rod_rounded_ends to draw the edges and vertices of a given graph. This approach only allows for straight edge embeddings of graphs. In general this will be of interest to me as I continue to look into panelled and flat graphs and their properties.

Thank you for reading! Keep checking back for more interesting graphs!

-Ben Flint

REFERENCES:

F Castagna, G Prins
Every generalized Petersen graph has a Tait coloring
Pacific J. Math., 40 (1972), pp. 53-58

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s