Some Doodles I'm Proud of -- The Capping Algorithm for Embedded Graphs
30 Mar 2025 - Tags: pretty-pictures
This will be a really quick one! Over the last two weeks I’ve been finishing up a big project to make DOIs for all the papers published in TAC, and my code takes a while to run. So while testing I would hit “go” and have like 10 minutes to kill… which means it’s time to start answering questions on mse again! I haven’t been very active recently because I’ve been spending a lot of time on research and music, but it’s been nice to get back into it. I’m especially proud of a few recent answers, so I think I might quickly turn them into blog posts like I did in the old days! In this post, we’ll try to understand the Capping Algorithm which turns a graph embedded in a surface into a particularly nice embedding where the graph cuts the surface into disks. I drew some pretty pictures to explain what’s going on, and I’m really pleased with how they turned out!
So, to start, what’s this “capping algorithm” all about?
Say you have a (finite) graph
Obviously every graph embeds into some high genus surface – just add an extra handle for every edge of the graph, and the edges can’t possibly cross each other! Also once you can embed in some surface you can obviously embed in higher genus surfaces by just adding handles you don’t use.
This leads to two obvious “extremal” questions:
- What is the smallest genus surface which
embeds into? - What is the largest genus surface which
embeds into where all the handles are necessary?
Note we can check if a handle is “necessary” or not by cutting our surface
along the edges of our graph. If the handle doesn’t get cut apart then our
graph
Defn: A
Then the “largest genus surface where all the handles are necessary” amounts
to looking for the largest genus surface where
And what is that algorithm? It’s called Capping,
see for instance Minimal Embeddings and the Genus of a Graph by
J.W.T. Youngs. The idea is to cut your surface along
The other day somebody on mse asked about this algorithm, and I had a lot of fun drawing some pictures to show what’s going on2! This post basically exists because I was really proud of how these drawings turned out, and wanted to share them somewhere more permanent, haha.
Anyways, on with the show!
We’ll start with an embedding of a graph 𝐺 (shown in purple) in a genus 2 surface:
we’ll cut it into pieces along
Now we choose3 a big submanifold
We glue all our pieces back together, but remove the interior of
and then, as promised “cap off” the boundary components
Note also that
Let’s squish it around to a homeomorphic picture, then do the same process a second time! But faster now that we know what’s going on:
At this point, we can try to do it again, but we’ll find that removing
This tells us the algorithm is done, since we’ve successfully produced a
2-cell embedding of
Wow that was a really quick one today! Start to finish in under an hour, but it makes sense since I’d already drawn the pictures and spent some time doing research for my answer the other day. Maybe I’ll go play flute for a bit.
Thanks for hanging out, all! Stay safe, and see you soon ^_^
-
This photo of a solution was taken from games4life.co.uk ↩
-
You know it’s funny, even over the course of drawing just these pictures the other day I feel like I improved a lot… I have half a mind to redraw all these pictures even better, but that would defeat the point of a quick post, so I’ll stay strong! ↩
-
It’s possible there’s a unique “best” choice of
and I’m just inexperienced with this algorithm. I hadn’t heard of it until I wrote this answer, so there’s a lot of details that I’m fuzzy on.If you happen to know a lot about this stuff, definitely let me know more! ↩