A caterpillar is simple to define: a graph in which the removal of all degree-1 vertices leaves a path. In a sense, it is the next best thing to a path. Several graph drawing algorithms that work for paths can be extended to work for caterpillars. I wonder when the first reference to caterpillar graphs occurred... The very hungry caterpillar has nice illustrations.
This is probably not the first reference to caterpillars, but it is at least 36 years ago: Harary and Schwenk, "The Number of Caterpillars," Discrete Mathematics v.6, p.359-365, 1973.
ReplyDelete