Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2010-007 (March 18, 2010)

Constant Time Generation of Rooted and Colored Outerplanar Graphs
by Jiexun Wang and Hiroshi Nagamochi

pdf File

An outerplanar graph is a graph that admits a planar embedding such that all vertices appear on the boundary of its outer face. Given a positive integer $n$ and a color set $C$ with $K>0$ colors, we consider the problem of enumerating all colored and rooted outerplanar graphs with at most $n$ vertices without repetition. We design an efficient algorithm that can generate all required graphs in constant time per each and in linear space.