Recently, I’ve come across some unusual types of graphs while solving problems. These graphs often had funny and/or cool names that I thought described what they look like quite well.
Today, I’ll share some of these graphs with you (along with some illustrations). If you feel like there are some other cool graphs I should add to this list, please comment them down below.
An onion is a graph where there are exactly 2 nodes with degree greater than 2. Every other node has degree 2. Every simple path between the 2 “endpoints” has equal length.
Onions are one of my favourite vegetables in real life, so naturally I quite like them. They’re also quite easo to work with (since one can just find the two “endpoints” and DFS).
The first (and only) time I used onions was in the 2016 Polish Olympiad in Informatics problem Amusing Journeys.
A cactus is a graph where each edge is part of at most 1 simple cycle.
Personally, I find cacti quite nasty to work with. They’re basically trees but with annoying cycles you have to deal with (just like how cacti are basically trees but toxic and painful to touch in real life). Some people (like Brian Chau) seem to love them for some inexplicable reason though.
A nice problem that uses cacti is the 2016 Polish Olympiad in Informatics problem Hydrocontest.
A caterpillar is a tree where each node is either part of or exactly 1 edge away from a “central path”.
(I couldn’t find a nice cartoon caterpillar so here’s a Wikipedia image :P)
I don’t have much to say about caterpillars. You should check out this other blog I found if you would like to learn more about caterpillars.
A nice problem that uses them is the 2016 International Olympiad in Informatics problem Shortcut.