Snakes

There are several different notions of snake graphs. In combinatorics snakes are finite subgraphs of the square grid formed by taking a union of cells, where a cell consists of four cyclically connected vertices of the grid and the edges that join them, and where the cells that form a snake can be ordered in a linear fashion, so that each cell is either immediately to the right of or immediately above the preceding cell.

Octopi

Keeping up with the marine theme, an octopus graph is similar to the jellyfish. This one is easier to define as it consists of a head, which is k-clique, and m tentacles of size t. The k-clique is a complete graph on k vertices and each of the tentacles is a path of length t. Note that for k=1 the octopus graph becomes a spider. These graphs occur in papers on neural networks and are of interest because of their large diameter and easy to parametrize density.

Jellyfish

Jellyfish graphs seem to be a fairly new idea. The term first appears around the turn of the century in an attempt to describe the topology of the Internet graph. The idea is that jellyfish graphs have a body (or cap) and lots of tentacles emanating from the core. In the case of the Internet, when looking at the Autonomous Systems level, the so called AS Internet graph can be thought of as a jellyfish graph. The Internet core corresponds to a clique or quasi-clique of high degree nodes. The rest of the graph can be seen as chains of lower degree nodes. Unlike other classes of graphs, jellyfish don't have a succinct definition. There is a formal definition here but it takes half a page and is not particularly pleasant.

Starfish

Starfish graphs are made of one central cycle and a bunch of tentacles. When drawn appropriately they can look like starfish. More formally, a starfish graph has k vertices of degree 4 and k vertices of degree 2, with the degree-4 vertices arranged in a cycle and the degree-2 vertices making up each tentacle. Setting k=5 yields the traditional 5-tentacled beast. Apparently, the H-cover problem is NP-Complete even for simple graphs like starfish.

Tadpoles

Tadpoles are graphs made of cycles and paths. The smallest tadpole is made of a cycle on three vertices joined with a path with just one edge. Bigger tadpoles can be obtained by making the cycle larger and/or the path longer. When the tail of the tadpole is made of just one edge, the graph is also known as a pan graph, with the tail playing the role of a pan-handle. Tadpole graphs have been mentioned in the physics literature and seem to date back to Feynman.

Snarks

Snarks are graphs with an interesting property related to graph coloring. One of the most fascinating coloring results, the four-color theorem states that every map can be colored with 4 colors so that no two neighboring countries have the same color. This is the same as saying that every planar graph can be vertex-colored with 4 colors so that no two adjacent nodes have the same color. The four-color theorem can be restated in terms of snarks as follows: no snark is planar. Informally, a snark is a graph in which every vertex has degree 3 and in which every 3-coloring of edges results in some pair of adjacent edges with the same color. Formally, a snark is a biconnected cubic graph with edge chromatic number 4. There are infinitely many snarks but Petersen's graph is the classic. Since the 70's a lot of strange-looking snarks have appeared in various papers: the Szekeres snark, the Blanusa snark, the Zemfirescu snark, Tietze's graph, etc. Tutte's conjecture that all snarks have the Petersen graph as a minor was proven by Robertson, Seymour and company and is now known as "the snark theorem." Snarks are non-planar and non-Hamiltonian. Even stronger, removing any one node from a snark leaves a Hamiltonian subgraph.

Centipedes

Centipedes are a subclass of caterpillars. A graph is a centipede if it can be obtained by appending a "leg" to each degree-2 node of a path. In reality they look like a centipede seen from the side at a moment when all its legs on one side occlude all its legs on the other side. I know they were used as far back as 1986 where they popped up in the characterization of the class of graphs that admit cylindric visibility representations.