Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2011-002 (January 12, 2011)

Indexing All Rooted Subgraphs of a Rooted Graph
by Tomoki Imada, Hiroshi Nagamochi

pdf File

Given a connected graph $G$ rooted with a designated vertex or a biconnected component, the descendants of a cut-vertex $v$ induces a connected subgraph rooted with the vertex $v$. We consider the set ${\cal R}$ of all such rooted subgraphs in $G$, and assign an integer, called an index, to each of the subgraphs so that two rooted subgraphs in ${\cal R}$ receive the same index if and only if they are isomorphic, where their roots correspond each other. In this paper, assuming a procedure for computing a signature of each graph in a class ${\cal G}$ of biconnected graphs, we present a framework for computing indices to all rooted subgraphs of a rooted graph which is composed of biconnected components from ${\cal G}$. With this framework, we can find indices to all rooted subgraphs of a rooted outerplanar graphs in linear time.