Welcome back!

My last blog post dealt with learning some of OpenSCAD to tackle the problem of representing graphs in 3D, culminating in some OpenSCAD code that would draw any generalized Petersen graph. To do so, I wrote code that would take in values for the parameters that define a Petersen graph and then use a dedicated loop to draw three edges of the graph at a time by rotating 360/n degrees each time the loop was run. This created a very interesting representation of a Petersen graph where the outer rim was drawn entirely on one plane with the edges approximating a circle and the inner rim was drawn on a plane that was parallel to the outer rim. The inner rim, when drawn in a plane, creates many intersection points between the edges of the rim. However, one might have reason to be interested in representing graphs in 3D without any intersections.

I have started working on the problem of representing general Petersen graphs without any intersections between the edges that make up the inner rim (recall that they take the form (i + k)’ where (i + k) is read mod n). One thing to note before I jump into how I represented these graphs is that the edges of the inner rim form a set of cycles, C. If k divides n then these cycles will be of length m where k * m = 0 mod n and |C| = k. If k does not divide n, then |C| = 1 and that cycle will have length m = n. Thus the inner rim of GP(12, 3) will have cycles of length m = 4 and |C| = 3.

Keeping that in mind, my first attempt at drawing Petersen graphs was to draw the distinct cycles on their own planes. However, this ONLY works for generalized Petersen graphs where k divides n, because as we saw, attempting to draw generalized Petersen graphs where k does not divide n with the single cycle in the plane results in many intersections. My first attempt at drawing these graphs works by raising each vertex by a set amount. To isolate the cycles, I realized that the distinct cycle starting at vertex i’ had vertices {i’, (i + k)’, (i + 2k)’, … , (i + (n-1)k)’}. I also noted that each one of these vertices is the same mod k. Then to correctly graph the distinct cycles, I changed the height of each point by a set amount depending on its value mod k. The results presented some very interesting examples of Petersen graphs, including the following:  The first of these examples is a representation of GP(12, 3), the second of GP(60, 4), and the third and fourth are of GP(60, 12) (the fourth is a top down view of GP(60, 12)). One interesting thing to note about the representation that I’ve chosen to implement is only partially successful at representing general Petersen graphs without any intersections. First there is the obvious issue that this code is severely limited in that it can’t represent any Petersen graph where k does not divide n. The second is that, even if given n and k such that k divides n, if the value of n is too large compared to the value of k, the cycles will be so long (have too many edges) that each edge will be short and intersect with the edges making the spokes of the graph. This can be seen in the second example, the representation of GP(60, 4), which I like to call “The Coliseum”. In “The Coliseum” each cycle has length 15 but there are only 4 such cycles.

I decided that the first of these issues that I would tackle would be that this code cannot represent generalized Petersen graphs for any valid values of n and k. In order to rectify this, I wrote a new function that assigned a different height to each vertex. Then I changed the function that drew the edges of the inner rim to modify the height based on its value (i + k)’ mod n. The resulting code could draw any generalized Petersen graph with valid values for n and k where the first half of the inner rim edges have rising height and the other half have descending height. This code is much more robust than the other code in that it can draw many more generalized Petersen graphs and still maintains the property that distinct cycles are all raised to different heights. However, given how close the rising edges are, the thickness of the edges had to be lowered significantly to avoid intersections. Consider the following three examples this code has produced:

At first glance, the first two pictures look like they represent the same graph, but on closer inspection, the first represents GP(11, 3) and the second represents GP(12, 3). A fine distinction, to be sure but note that GP(11, 3) only has one distinct cycle, whereas all three distinct cycles of GP(12, 3) can be picked out. The third example represents GP(60, 12). Given the perspective of the picture, it can be difficult to see, but this graph is embedded with no intersections. The resulting graph looks a lot like a structure that is being suspended by tightly knit steel cables that are under tension. Though this code is more robust in the amount of Petersen graphs that it can represent, it is still plagued by the issue of drawing Petersen graphs with large values of n and small values of k without intersections.

For next week, I intend to move away from Petersen graphs and start working on representing examples of flat and panelled graphs following along with the paper On n-panelled spatial graphs, n-flat graphs and graph minors by Ryo Nikkuni and Yukihiro Tsutsumi.

As always, thank you for reading!

-Ben Flint

REFERENCES:

Nikkuni, Ryo, and Yukihiro Tsutsumi. “On n-Panelled Spatial Graphs, n-Flat Graphs and Graph Minors.” preprintWeb.