Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2009-018 (December 12, 2009)
Enumerating Rooted Biconnected Planar Graphs with Internally Triangulated Faces
by Bingbing Zhuang and Hiroshi Nagamochi
A graph is called a triangulated planar graph
if it admits a plane embedding in the plane such that
all inner faces are triangle.
In a rooted triangulated planar graph,
a vertex and two edges incident to it
are designated as an outer vertex and outer edges,
Two plane embedding of rooted triangulated planar graphs are defined to be
equivalent if they admit an isomorphism
such that the designated vertices correspond each other. Given a positive integer $n$, we give an algorithm for
enumerating all plane embeddings of
rooted, biconnected and triangulated planar graphs with at most $n$ vertices
without delivering two equivalent embeddings.
The algorithm runs in constant time per each by outputting
the difference from the previous output.