Today’s mission was to transform K₆ into another member of the Petersen Family of graphs using a Δ-Y transform of K₆ by identifying 3 vertices and 3 edges connecting them pair-wise, deleting those edges, and adding a new vertex connected to all three points. My starting point for this is my OpenSCAD code from making  K₆ . Want I wanted to do was delete the edges in red and add a new vertex in the center and in blue add three new edges to connect the new vertex with the three vertices whose edges I pairwise deleted. The picture below nicely shows the Δ-Y transform of K₆ that would be taking place.

My current issue is this: the way my code is set up, I have all my edges being created by a for loop.

I got stuck trying to figure out how to easily delete three edges after they had already been made. I’m going to talk with Dr. Taalman to see if there is a quick fix or how I should efficiently writing code to make this transform happen.

Until next time,

Hannah Critchfield

This week was largely spent on cleaning up my code for the Petersen graph and the graph of K₆ (also I changed how K₆ looks as a 3-D model completely). Since I am very new to OpenSCAD, my code was very length and a lot of it was unnecessary. I saved well over 40 lines in total between the two graph codes. Over spring break I hope to work on the other members of the Petersen family of graphs, now that I know how to speed up the process with for loops in OpenSCAD.

New K₆ Graph and Code

In last week’s post, the gif of K₆ was all over the place. There wasn’t much symmetry to the graph in my model of it. Dr. Taalman suggested I position the points around a circle, rather than just winging the coordinates. this resulted in a much better representation of K₆ (see gif below).

And here is the (much shorter) code that made the new representation of K₆! 

For the Petersen graph, I tidied up the code in the same fashion. The actual representation of it looks the same overall, just a bit bigger now that my code has a parameter section and due to the fact we are looking to print out these models.

Until next time,

Hannah Critchfield

Graphs can be a funny thing. When you say “graph”, some people will thing of a line or some other function in 2-D. Other people will think of marvelous planes and surfaces in 3-D. Fewer people will think of “standard” graph theory type graphs represented in 2-D. And even fewer people will think of those graph theory type graphs represented in 3-D. My goal is to change that.

Throughout the semester, I want to highlight the Y-Δ and Δ-Y transforms that allow you to go between graphs within the Petersen family of graphs. The names Y-Δ and Δ-Y are quite visual. In Y-Δ you are replacing 4 vertices that make a Y shape with 3 that make a triangle shape and in Δ-Y you are replacing 3 vertices that make a triangle shape with 4 that make a Y shape. Now, when the Petersen family of graphs are represented in 2-D, these Y-Δ and Δ-Y transforms are not quite apparent. I am hoping that representing these graphs in 3-D will make these transforms a bit clearer.

Since this is my first exposure to OpenSCAD (and really my first exposure to modeling something in 3-D all my own), I’m going to start off the semester by getting the Petersen family of graphs in 3-space and then go from there. This week we have the famous Petersen graph and K₆ being featured.

The Petersen Graph

Bringing the Petersen graph into 3 dimensions was quite exciting. The Petersen graph is classically portrayed as a big pentagon with a small star in the middle, like this:

As you might be able to guess, the Petersen graph is nonplanar. We can’t draw it on a plane without its edges overlapping. However, if we allow ourselves an extra dimension, we can represent the Petersen graph without any edges overlapping. 

Just like in 2-D, there are different ways to represent the Petersen graph in 3-D. Above is the one I chose to start my OpenSCAD intro with. I created it using an edge code my mentor, Dr. Taalman, sent me. Here’s a picture of my code!

K₆

Now, even though K₆ doesn’t look as complicated as the Petersen graph (it only has 6 vertices!), it is much more complicated to graph in 3-D while avoiding edges crossing over. The view from the top down doesn’t look like K₆ ,but when you move ever so slightly, you can see edges that weren’t visible before.

With the Petersen graph, I only had to adjust the height of a few points. However, K₆ is a completely different beast in that regard. Here is a spin around the graph! As you’ll be able to see, K₆ in 3-D (or at least how I’ve represented it, there are probably cleaner ways) gets pretty intricate compared to the Petersen graph above!

 

Hopefully next time I will have the other 5 graphs from the Petersen family to show you all, since I am much more familiar with OpenSCAD. I can tell that showing of the Y-Δ and Δ-Y transforms will be a challenge — but I’m excited!

Until next time,

Hannah Critchfield

My first ever exposure to any sort of graph theory was through this paper by Flapan, Mattman, Mellor, Naimi, and Nukkuni. If you’ve already clicked on the link, you might see how someone could get overwhelmed with terminology early on in the paper. Since I had no prior knowledge to graph theory, that person was me. The goal of this post is to provide some casual definitions and some examples showing off certain properties. (Note: this will not cover all definitions in the paper, and certainly not all definitions in graph theory, just some ones that I wish I knew before reading the paper/some ones I think need extra attention.)

[Note: all images are either from the paper linked above, or are from the wikipedia article linked in the definition title preceding the image.]

Definitions and Examples

Planar Graph: A graph is planar if it can be drawn on the plane without any of its edges crossing. (Note: only one way of drawing the graph without the edges crossing has to exist for it to be planar.)

K_n: This is a complete graph with n vertices. It will also have n(n-1)/2 edges. Below is a picture showing off K_n for n=1…12 along with the number of edges the graph has._for 

Minor: Let G be a graph and H be a subgraph. A minor of a graph is created by deleting edges and vertices, and contracting zero or more edges. (Note: when you contract an edge, the two vertices at the end of that edge merge.) Below is a diagram of a G: graph, H: minor of G, and how the minor was formed. The dotted line represents the deletion of an edge, while the grey line represents the contraction of an edge.

Y-Δ Transform/Move: Let G be a graph that has a vertex, v, and let v have exactly three other vertices surrounding it. A Y-Δ transform of G at v is achieved by removing v from G and adding edges between each pair of the neighboring vertices.

Δ-Y Transform/Move: Let H be a graph that has a triangle of vertices, uvw. A Δ-Y transform of H at uvw is achieved by removing the edges uv, vw, and uw from H and adding a new vertex, z,  and new edges uz, vz, and wz.

So, in Y-Δ transforms you are deleting a vertex and in Δ-Y transforms you are adding a vertex. These transforms will be useful for understanding an upcoming definition.

Petersen Graph: This is a graph with 10 vertices and 15 edges. Click on the link and scroll to read about some neat properties Petersen Graphs have. If I listed them all here, this definition would be the length of the blogpost.

Petersen Family of Graphs: This is a set of seven undirected graphs (graphs in which the edges don’t have direction) that includes the Petersen graph, the complete graph K₆  and 5 other graphs that are formed by Y-Δ and Δ-Y transforms. Below are two images: one from the paper mentioned at the beginning of this post and one from the Wikipedia page linked in this definition. Both show the Petersen family of graphs, but the Wikipedia picture shows which graphs can be formed by performing Y-Δ and Δ-Y transforms.

Upcoming

If you clicked on the paper mentioned at the beginning of the blog post, you may have noticed that the definitions featured here only cover the first three pages. These definitions and examples were chosen because they are going to be heavily used in what I want to do next. Past posts by Ben Flint have shown off Petersen graphs represented in 3-dimensions. My goal for the semester is to represent K₆ , K_3,3,1 , a Petersen graph, and the other 4 graphs in the Petersen family in 3-dimensions. A stretch goal/side project is to create some sort of program that will perform those Y-Δ and Δ-Y transforms on the Peterson family of graphs (and potentially others as well).

 

Until next time,

Hannah Critchfield