The recognition of double Euler trails in series-parallel networks

Abstract

Given a series-parallel network (network, for short) N,its dual network N' is given by interchanging the series connection and the parallel connection of network N. We usually use a series-parallel graph to represent a network Let G[N] and G[N'] be graph representations of N and N', respectively. A sequence of edges e(1), e(2),...,e(k) is said to form a common trail on (G[N],G[N']) if it is a trail on both G[N] and G[N']. If a common trail covers all of the edges in G[N] and G[N'], it is called a double Euler trail. However, there are many different graph representations for a network. We say that a network N has a double Euler trail (DET) if there is a common Euler trail for some G[N] and some G[N']. Finding a DET in a network is essential for optimizing the layout area of a complementary CMOS functional cell. Maziasz and Hayes (IEEE Trans. Computer-Aided Design 9 (1990), 708-719) gave a linear time algorithm for solving the layout problem in fixed G[N] and G[N'] and an exponential algorithm for finding the optimal cover in a network without fixing graph representations. In this paper, we study properties of subnetworks of a DET network. According to these properties, we propose an algorithm that automatically generates the rules for composition of trail cover classes. On the basis of these rules, a linear time algorithm for recognizing DET networks is presented. Furthermore, we also give a necessary and sufficient condition for the existence of a double Euler circuit in a network. (C) 1998 Academic Press.