Student Post: Visualizing Bipartite and Complete Graphs in 3D Space

Bipartite Graphs

When thinking about how to represent bipartite graphs in 3D space, the challenge arose: how do we take full advantage of this extra dimension. The models we started with worked fine as they were, but we weren’t fully satisfied. As seen below, our current model for the graph K44 appeared in space as two graphs of K22 stacked on top of one another and rotated 45 degrees. We knew we could do better.

Original graph for K44

What followed was a simple, yet elegant solution to the problem. For a graph KNM, the points N are plotted along the Z axis while the points M are plotted along a circle around the origin. What resulted can be seen below in our new graph for K33.

K33 using the Line and Circle model

3D printing the graph for K33 only solidifies the simplicity of the design; however, the true beauty of the design is how it can be adapted to a general solution for all values of KNM

The Line and Circle Model

K5-5 using the Line and Circle model

The line and circle model is perfect for relatively small values of KNM as it clearly displays the relationship every point has with each other. However, for increasingly larger graphs, It becomes clear that points plotted along the line are allocated significantly less space than those along the circle. As such the points may begin to appear unevenly distributed as the size increases. This can be useful, for displaying graphs KNM where N and M are different values, such as K6-10.

The Semicircle Model

After developing and printing graphs for the Line and Circle model, we had a desire to iterate upon its design. Our original idea involved plotting the points of K33 on the vertices of an octehedron, but the model itself soon generalized to plotting the points of the graph along opposing, perpendicular semicircles. As such is distributes the vertices of the graph evenly across the model. The semicircle model is more suitable for visualizing larger graphs, but can feel rather sparse for smaller values such as K33. Graphs of KNM where N and M are not even can also appear lopsided, as the nature of the semicircle model’s visual symmetry relies upon the two plots being equal.

K55 Using the semicircle model

Streamlining the Code

After developing our two models for bipartite graphs, our next objective was to make it easier and less time consuming to create graphs in openSCAD. Up to this point, we had been manually plotting points in the code. While we already had code to connect lines between points, meaning most of the hard work was already done, for the work of plotting points for each (increasingly large) new graph we wanted to print was still very time consuming. It would be entirely impractical to plot something as large as K20-20 for instance without more advanced code.

K20-20 Using the semicircle model

I developed the code to the point where for any two values for KNM, the program would automatically create the corresponding graph in either model and scales it appropriately.

Below is the code for plotting a graph using the line and circle model. This was easily the most complicated part of the process, as it required splitting the points into 3 separate variables. The variable k plots all of the Line vertices while v and z each plot half of the circle vertices.

Because these two models for bipartite graphs could be generalized so easily, we were able to write code that could plot a graph of any size in seconds. Having reached a good stopping place for bipartite graphs, we began looking towards modeling complete graphs.

Complete Graphs

Immediately it became apparent that generalizing a model for complete graphs would be quite unfeasible, as applying any really symmetry to them would result in intersections. We still wished to generalize them in some way, and while the first model we arrived at did have some merits, it was not quite satisfactory. We called this model the Dome Projection of a complete graph.

Dome Projection

The idea behind the Dome Projection model to plot the vertices of the graph on a circle, then connect them by projecting their edges on different ‘dome levels’. The code for it works by starting from a single vertex and connecting it to every other point. It then increases the dome level, moves to the next vertex and connects it to every vertex it is not yet connected to, proceeding like this until ever vertex is connected to every other vertex.

Dome Projection for K5

One interesting thing about the Dome Projection is its relation to another way of representing graphs, the Book Embedding method.

A Book Embedding of K5

Book embedding works by connecting the vertices of a graph on different planes or ‘sheets’, connecting all possible points to each other without intersections then moving onto the next sheet and proceeding in this way until every vertex is connected. We quickly discovered that the number of sheets in a book embedding corresponded to the number of levels on a dome projection. As seen above, the dome projection for K5 has 3 levels while the book embedding has 3 sheets.

Dome projection serves as an interesting new way to represent graphs and certainly looks nicer on a desk than a book embedding, however it was still not quite what we were looking for from a 3D modeling of complete graphs.

A Better Representation

Even though its unlikely a generalized form for the complete graphs exist in 3D space, we sought to find something close, at leas for relatively small values of K. Starting with K6, The first model we constructed involved plotting pairs of points at different Z values and rotating them around the Z axis. What resulted appeared as a tetrahedron with two points inside of it. This tetrahedral visualization for K6 attempts to preserve as much symmetry as possible in the graph with hopes that doing so could provide a method to visualize large KN graphs, such as K8, with as much order as possible. This visualization does work well for K6 but does begin falling apart at K8. Though no graphs larger than K8 have been modeled in this way yet, it’s safe to say this trend would continue.

Plotting K8 with the tetrahedral visualization

Our second visualization for K6 takes things in a different direction. Instead of generalizing a model for the graph, it aims to generalize an algorithm for determining the model for each individual graph. The code we used for it plots the points of the graph randomly on a sphere then calculates the distances between every edge for a given number of trials. The model that has the largest distances between edges is selected as the new best model for a given graph. It takes millions of trials to get a reasonable result, however, that result it striking .

Two Visualizations for K6

Order and Disorder in 3D Graphs

On the left is the graph for K6 we started with when this project began. It was created by stacking two graphs for K3 on top of each other and rotating them so that their edges don’t intersect. On the right is the graph for K6 that our code produced. After a semester and a half, we ended up exactly where we started. There’s some beauty in this, however, as somehow, a model created through order and a model created through chaos ended up appearing strikingly similar. This could just be coincidence, or it could be a result of the absurd poetry that is Math.

Looking to the Future

As we move forward in this project, we plan to continue finding new models for larger complete graphs. We’re excited to see what these graphs end up looking like, as everything after K6 is new territory at this point.

Rocket Flame Trench 3D Printing Project

Last semester as well as this semester, I have been working with Dr. Taalman to produce a 3D printed model of the rocket flame trench that is located at the launchpad in NASA’s Wallop Flight Facility on Eastern Shore Virginia. When a rocket is launched it generates a lot of heat, and the trench directs the exhaust and heat away from the rocket.  

Dr. Lubert, who is currently researching how to minimize the vibration caused by the rocket launch noise, gave us several blueprints and pictures of the trench. This gave us an idea of the shape of the trench.

Our first step was to see if Fusion 360 had the tools we needed to design the model. We tested our idea on how to build the model in Fusion 360 and printed an object that has a similar shape as the trench.

After we had figured out that we could design the model in Fusion 360, we scanned the blueprints and up loaded them to the Fusion 360 cloud. Since the blueprints contain proprietary information, we also removed all the measurements from the blueprints in case Fusion 360 was hacked and the blueprints stolen.  (The blueprints will be available at the presentation.)  

Once the blueprints were in Fusion 360, we sketched the shape of the trench by tracing over the blueprints. Since we do not have blueprints for the cross sections of the trench and for the top, we will need to use available pictures to help us to determine the shape of these sections

At this point, the side section of trench has been sketched. The top and front sections still need to be sketched. Once the model has sketched and the different planes connected to a make a 3D model, the model will be ready to print.  The printed model will give Dr Lubert a better understand of the shape of the trench and how a rocket’s exhaust flow through and exits the trench.


Photo Credits: Dr. Lubert and Lyndon Swarey

Student Post: Rolling Trefoil Knots


Dr. Laura Taalman and Dr. Stephen Lucas have been researching rolling trefoil knots since before we (Abby Eget and Harley Meade) became involved with the project. When we joined the research team, we were fortunate enough to come into the project with a lot of previously coded information in OpenSCAD including the general shape of the Morton trefoil, which is tritangentless, which is what allows it to properly roll. Then we helped the team optimize the knot using a parameter a, in accordance to the formula in the section below, so that there was minimal variation in the height of the center of mass.

Optimizing the z value using the a value:

Originally the plan was to optimize the a value by scaling by 1 in the z direction. This was done surprisingly quickly, so we shifted directions. Instead of optimizing the a value for scaling by 1 in the z direction, we decided to try to optimize the scaling in the z direction based on varying a values. We used a values of 0.3, 0.5, 0.7, and 0.9.

Coded knot with a = .5

We printed the four trefoil knots with the four different a values from Shapeways. Then we printed four corresponding convex hulls in our own Maker Lab. These are pictured below.

This image has an empty alt attribute; its file name is img-6355-e1553031369202.jpg
a = .3 scaling = .4629
This image has an empty alt attribute; its file name is img-6356-1-e1553031560633.jpg
a = .5 scaling = .8210
This image has an empty alt attribute; its file name is img-0232-1-e1553031667294.jpg
a = .7 scaling = 1.3162
This image has an empty alt attribute; its file name is img-0231-1-e1553031817729.jpg
a = .9 scaling = 2.4954
This image has an empty alt attribute; its file name is graphcomparingknotssnip.png
Varying heights of the center of mass for knots of varying a values with z-scale 1.

Knot paths:

After considering how the knots rolled in relation to their convex hulls, we decided to use the triangles from the convex hulls’ code to see what kind of paths the knots make when rolling on the table. Two of these are pictured below, with the black line showing the horizontal shift in center of mass.

This image has an empty alt attribute; its file name is knotpathssnip.png
Path of Morton trefoil knots with a = 0.3 and a = 0.5

Two other parameters that we changed are the p and q values of the knots. These are related to the fact that the trefoil is a torus knot, where the p represents how many times the knot wraps around a torus meridianally and the q represents how many times the knot wraps around the torus longitudinally. We also decided to change these values, while keeping p and q relatively prime so as to not go from a knot to a link, to see if these knots would at least be externally tritangentless, and how their paths on a table would be affected.

This image has an empty alt attribute; its file name is img-0233-1-e1553033443463.jpg
p = 7 q =2

After exploring some of the variables and parameters surrounding rolling trefoil knots, we are excited to continue optimizing these knots by looking at other factors. In the future, we plan to optimize the materials, infill, and consistency in sizing of the knots to minimize differences not currently accounted for.

Welcome Back

Hello all,

It has been a long time. I took a break from KoebeLib to research another problem and now I am back! Man, oh man, has it been a long time and I am happy to let you know that a lot has been done since my last post. We are well past our way of selecting circles. The selection of circles then allowed us to create more sophisticated tools. Current functionality includes: calculating the intersection of two circles, given two disks and a point the member of the coaxial family through that point is calculated, and we have delete functionality! Below a picture has been included to show you what the current button panel looks like when it is first run. The current in progress tools are given two disks and a point calculate the disk of the orthogonal family. We initially thought that we could use the conical caps to calculate, however, this did not work. Our next thought is that we calculate the plane orthogonal to the given two disks and this will be relatively simple because we had to do something similar for the member of the coaxial family. We have code written for given three disks return a c-plane but there is not currently a button for it because we aren’t quite sure as to how to represent c-planes. On the flip side another tool in progress is given three c-planes return a disk. For this to be completed I just have to write the calculation to select a plane. These two tools will not require too much work and as a result I have a couple more (simple) things in progress. Currently our button panel is not responsive so that is first on my todo list. We also want a side panel that displays the current drawn objects and want functionality to be able to select multiple objects. I will see you all with more tools completed for KoebeLib.

Screen Shot 2019-03-04 at 5.28.29 PM

Until then,

Madelaine Brower