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.

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.

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

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.

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.

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

https://en.wikipedia.org/wiki/Book_embedding

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.

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

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.

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 .

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.