On a Characterization of Series-Parallel Graphs

Let \(G\) be a connected graph and \(T\) be a spanning tree of \(G\). (Here, trees and cycles are equated with their edge sets.) Then, the gi-pair \((G,T)\) is a dfs-pair if there exists a digraph \(D\) such that the underlying graph of \(D\) is \(G\), \(T\) is a rooted-ditree in \(D\), and every fundamental cycle of \((G,T)\) is a dicycle of \(D\). Two gi-pairs \((G,T)\) and \((G’,T)\) are cycle-isomorphic if there is a 1-1 mapping between \(Z(G)\) and \(Z(G’)\) so that \((G,T)\) and \((G’,T)\) have the same sets of fundamental cycles. Shinoda, Chen, Yasuda, Kajitani, and Mayeda [6] showed that a 2-connected graph \(G\) is series-parallel if and only if for every spanning tree \(T\) of \(G\), the gi-pair \((G,T)\) is cycle-isomorphic to a dfs-pair. In this paper, an alternate proof of this characterization is given. An efficient algorithm to find such a cycle-isomorphic dfs-pair is also described.