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.
No comments:
Post a Comment