Saturday, February 28, 2009
Caterpillars
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.
Subscribe to:
Posts (Atom)