Week 2: Some Coding Has Appeared?!

Welcome back to my blog! 

In the past week, I realized just how much terminology I was lacking for graph theory (serves me right for studying topology instead I guess). Be it rotation systems of a vertex or facial walks – which I’ll spare you the details of – learning the nuances and equivalent definitions of each term was quite a pain, but it’s finally starting to piece itself together through all the papers I’ve been reading.

A Generating Algorithm For Polyhedral Embeddings

I spent most of my time reading a paper by Brinkmann et al., which provided an algorithm for generating polyhedral embeddings of cubic graphs (see previous post for definitions). The paper uses an equivalent definition of polyhedral embedding (for cubic graphs), which requires that all facial walks are cycles and any two walks are either disjoint or intersect at a vertex or edge. A facial walk can just be thought of as walking along the edges of a face in given direction as shown below.

A facial walk around a pentagonal face

The algorithm then takes advantage of a result by Mohar and Vodopivec about 3, 4, and 5 cycles being faces in polyhedral embeddings to define equivalence classes of vertices. More specifically, if any two vertices belong to the same 3, 4, or 5 cycle, we view them as the “same.” It turns out that these “same” vertices must all have the same rotation system, which is basically a way of ordering edges at a vertex in a clockwise manner. Then, using a recursive program, we can check the rotation systems for consistency, and with the help of some other results about cubic graphs, the search is much faster than brute force. So far, the code has confirmed Grünbaum’s conjecture for all cubic graphs with up to 36 vertices. 

While reading through this paper, I saw a reference to another recent work by Brinkmann on a generating algorithm that I will investigate. Afterwards, I am going to try an implement the algorithm in Python, though I’m not sure how well that’ll go. See you next week and feel free to ask questions! 

References

1. Brinkmann, G., Tucker, T.W., & Cleemput, N.V. (2020). On The Genera Of Polyhedral Embeddings Of Cubic Graph. Discret. Math. Theor. Comput. Sci., 23.