Embeddings of circulant networks

Abstract

In this paper we solve the edge isoperimetric problem for circulant networks and consider the problem of embedding circulant networks into various graphs such as arbitrary trees, cycles, certain multicyclic graphs and ladders to yield the minimum wirelength.

1 Introduction

Graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. A parallel algorithm can be modeled by a task interaction graph, where nodes and edges represent tasks and direct communications between tasks, respectively. Thus, the problem of efficiently executing a parallel algorithm A on a parallel computer M can be often reduced to the problem of mapping the graph G, representing A, on the graph H, representing M, so that the communication overhead is minimized. This is called graph embedding (Opatrny and Sotteau 2000), which is defined more precisely as follows:

Let G(V,E) and H(V,E) be finite graphs with n vertices. An embedding f of G into H is defined (Bezrukov et al. 1998) as follows:

• 1. f is a bijective map from V(G)→V(H)

• 2. f is a one-to-one map from E(G) to {P _f (f(u),f(v)):P _f (f(u),f(v)) is a path in H between f(u) and f(v) for (u,v)∈E(G)}.

Here G is called the guest graph and H, the host graph. The edge congestion of an embedding f of G into H is the maximum number of edges of the graph G that are embedded on any single edge of H. Let EC _f (G,H(e)) denote the number of edges (u,v) of G such that e is in the path P _f (f(u),f(v)) between f(u) and f(v) in H. In other words,

$$\mathit{EC}_{f}(G,H(e))=\vert \{ (u,v)\in E(G):e\in P_{f}(f(u),f(v))\} \vert $$

where P _f (f(u),f(v)) denotes the path between f(u) and f(v) in H with respect to f. For convenience of notation we write EC _f (e) instead of EC _f (G,H(e)) in the sequel.

If we think of G as representing the wiring diagram of an electronic circuit, with the vertices representing components and the edges representing wires connecting them, then the edge congestion EC(G,H) is the minimum, over all embeddings f:V(G)→V(H), of the maximum number of wires that cross any edge of H (Bezrukov et al. 2000a).

The Wirelength Problem

The wirelength (Manuel et al. 2009) of an embedding f of G into H is given by

$$\mathit{WL}_{f}(G,H)=\underset{e\in E(H)}{\sum }\mathit{EC}_{f}(e)=\underset{(u,v)\in E(G)}{\sum} d_{H}(f(u),f(v))$$

where d _H (f(u),f(v)) denotes the length of the shortest path P _f (f(u),f(v)) in H. See Fig. 1. Then, the minimum wirelength of G into H is defined as

$$\mathit{WL}(G,H)=\min \mathit{WL}_{f}(G,H)$$

where the minimum is taken over all embeddings f of G into H. The wirelength problem (Bezrukov et al. 1998, 2000a; Chavez and Trapp 1998; Manuel et al. 2009; Opatrny and Sotteau 2000; Rajasingh et al. 2004) of a graph G into H is to find an embedding of G into H that induces the minimum wirelength WL(G,H).

Fig. 1

Wiring diagram of a hypercube G into a cycle H with WL _f (G,H)=20. The edge congestions are marked on the edges of H

The wirelength of a graph embedding arises from VLSI designs, data structures and data representations, networks for parallel computer systems, biological models that deal with cloning and visual stimuli, parallel architecture, structural engineering and so on (Lai and Williams 1999; Xu 2001).

Grid embedding plays an important role in computer architecture. VLSI Layout Problem (Bhatt and Leighton 1984), Crossing Number Problem (Djidjev and Vrto 2003), Edge Embedding Problem (Garey and Johnson 1979) are all a part of grid embedding. Embedding problems have been considered for binary trees into paths (Lai and Williams 1999), complete binary trees into hypercubes (Bezrukov 2001), tori and grids into twisted cubes (Lai and Tsai 2010), meshes into locally twisted cubes (Han et al. 2010), paths into twisted cubes (Fan et al. 2007), cycles into twisted cubes (Fan et al. 2008), meshes into faulty crossed cubes (Yang et al. 2010), star graph into path (Yang 2009), snarks into torus (Vodopivec 2008), generalized ladders into hypercubes (Caha and Koubek 2001), grids into grids (Rottger and Schroeder 2001), binary trees into grids (Opatrny and Sotteau 2000), hypercubes into cycles (Chavez and Trapp 1998), generalized wheels into arbitrary trees (Rajasingh et al. 2004), and hypercubes into grids (Manuel et al. 2009). Even though there are numerous results and discussions on the wirelength problem, most of them deal with only approximate results and the estimation of lower bounds (Bezrukov et al. 1998; Chavez and Trapp 1998). All the embeddings discussed in this paper produce exact wirelengths.

Another interesting NP-complete problem (Garey and Johnson 1979) is the edge isoperimetric problem (Harper 2004) which will be used to solve the wirelength problem. We consider the following version of the edge isoperimetric problem of a graph G(V,E).

Find a subset of vertices of a given graph, such that the number of edges in the subgraph induced by this subset is maximal among all induced subgraphs with the same number of vertices. Mathematically, for a given m, if I _G (m)=max _A⊆V,|A|=m |I _G (A)| where I _G (A)={(u,v)∈E:u,v∈A}, then the problem is to find A⊆V such that |A|=m and I _G (m)=|I _G (A)|. We call such a set A optimal. Further for regular graphs a subset of vertices A is optimal, then its complement V╲A is also an optimal set (Bezrukov et al. 2000b; Bezrukov and Elsässer 2003). In the literature, this problem is also defined as the maximum subgraph problem.

2 Background

Lemma 1

(Congestion lemma) (Manuel et al. 2009)

Let G be an r-regular graph and f be an embedding of G into H. Let S be an edge cut of H such that the removal of edges of S leaves H into 2 components H ₁ and H ₂ and let G ₁=f ⁻¹(H ₁) and G ₂=f ⁻¹(H ₂). Also S satisfies the following conditions:

• (i) For every edge (a,b)∈G _i , i=1,2,P _f (f(a),f(b)) has no edges in S.

• (ii) For every edge (a,b) in G with a∈G ₁ and b∈G ₂, P _f (f(a),f(b)) has exactly one edge in S.

• (iii) G ₁ is a maximum subgraph on k vertices where k=|V(G ₁)|.

  Then EC _f (S) is minimum and EC _f (S)=rk−2|E(G ₁)|.

Lemma 2

(Partition lemma) (Manuel et al. 2009)

Let f:G→H be an embedding. Let {S ₁,S ₂,…,S _p } be a partition of E(H) such that each S _i is an edge cut of H. Then

$$\mathit{WL}_{f}(G,H)=\overset{p}{\underset{i=1}{\sum }}\mathit{EC}_{f}(S_{i}).$$

Lemma 3

(Generalized Partition lemma)

Let f:G→H be an embedding. For 1≤i≤k, suppose $S_{i}=\{S_{1}^{i},S_{2}^{i},\ldots,S_{p_{i}}^{i}\}$ partitions E(H)∖F _i for mutually disjoint F _i ’s such that $S_{j}^{i}$, 1≤j≤p _i , 1≤i≤k and $S=\bigcup _{i=1}^{k}F_{i}$ are all edge cuts of H. Then

$$\mathit{WL}_{f}(G,H)=\frac{1}{k}\left[ \overset{k}{\underset{i=1}{\sum }}\overset{p_{i}}{\underset{j=1}{\sum }}\mathit{EC}_{f}(S_{j}^{i})+\mathit{EC}_{f}(S)\right] .$$

Proof

For 1≤i≤k, we have

$$\mathit{WL}_{f}(G,H)=\overset{p_{i}}{\underset{j=1}{\sum }}\mathit{EC}_{f}(S_{j}^{i})+\mathit{EC}_{f}(F_{i}).$$

By summing up for all i, we get

Therefore

$$\mathit{WL}_{f}(G,H)=\frac{1}{k}\left[\overset{k}{\underset{i=1}{\sum }}\overset{p_{i}}{\underset{j=1}{\sum }}\mathit{EC}_{f}(S_{j}^{i})+\mathit{EC}_{f}(S)\right] .$$

 □

Remark 1

When k=1, we obtain the Partition lemma.

3 Edge isoperimetric problem for circulant networks

In 2004, L.H. Harper (2004) quotes “In analyzing Harary graph he wished to solve its edge isoperimetric problem”. In this section we solve the maximum subgraph problem for circulant networks which is a particular class of Harary graphs.

Definition 1

(Xu 2001)

A circulant undirected graph, denoted by G(n;±S) where S⊆{1,2,…,⌊n/2⌋}, n≥3 is defined as a graph consisting of the vertex set V={0,1,…,n−1} and the edge set E={(i,j):|j−i|≡s(mod n), s∈S}.

The circulant graph shown in Fig. 2 is G(10;±{1,2,3}). It is clear that G(n;±1) is the undirected cycle C _n and G(n;±{1,2,…,⌊n/2⌋}) is the complete graph K _n . Further G(n;±{1,2,…,j}), 1≤j<⌊n/2⌋, n≥3 is a 2j-regular graph.

Fig. 2

Circulant graph G(10;±{1,2,3})

Lemma 4

Let C denote the cycle G(n;±1) in G(n;±{1,2,…,j}), 1≤j<⌊n/2⌋, n≥3. Let K ₁ and K ₂ be disjoint segments induced by k ₁ and k ₂ consecutive vertices on C respectively such that k ₁+k ₂≤⌊n/2⌋. Then G[K ₁∪K ₂], the subgraph induced by K ₁∪K ₂, contains a vertex of degree at most j.

Proof

Let the complement of K ₁∪K ₂ in C consist of two disjoint segments D ₁ and D ₂ induced by d ₁ and d ₂ consecutive vertices on C respectively. Then d ₁+d ₂≥⌈n/2⌉. Without loss of generality, let $k_{2}\leq \frac{1}{2}\lfloor n/2\rfloor$ and $d_{2}\geq \frac{1}{2}\lceil n/2\rceil$. This implies k ₂≤d ₂. Suppose k ₁=1 and K ₁={u}. Then

$$\deg _{G[K_{1}\cup K_{2}]}u=\left\{\begin{array}{l@{\quad }l}2j-(d_{1}+d_{2}) & d_{1},d_{2}\leq j \\[2pt]0 & d_{1},d_{2}\geq j \\[2pt]j-d_{1} & d_{2}\geq j,d_{1}\leq j \\[2pt]j-d_{2} & d_{1}\geq j,d_{2}\leq j\end{array}\right.$$

But 2j−(d ₁+d ₂)≤2j−⌈n/2⌉≤2j−j=j. Therefore $\deg _{G[K_{1}\cup K_{2}]}u\leq j$. The same argument holds when k ₂=1. We now assume that k ₁≥2 and k ₂≥2. Let a,b be the end vertices of K ₁ and α, β be the end vertices of K ₂ taken in the clockwise sense. See Fig. 3(a). We claim that $\deg _{G[K_{1}\cup K_{2}]}\beta \leq j$.

Fig. 3

(a) K ₁,K ₂,D ₁ and D ₂ are disjoint segments on C (b) d ₂≥j, (c) u∈K ₁, v∈D ₁

Case 1 (d ₂≥j): In this case $\deg _{G[K_{1}\cup K_{2}]}\beta \leq j$. See Fig. 3(b).

Case 2 (d ₂<j): Let u be a vertex on C such that d _C (β,u)=j measured in the clockwise direction and let the shortest path of length j on C with origin β and passing through α have its other end at v.

Subcase 2.1 (v∈K ₁): In this case u∈K ₁. Therefore $\deg _{G[K_{1}\cup K_{2}]}\beta \leq 2j-(d_{1}+d_{2})\leq j$.

Subcase 2.2 (v∈D ₁): If u lies on K ₁ then $\deg _{G[K_{1}\cup K_{2}]}\beta \leq (k_{2}-1)+j-d_{2}$. But (k ₂−1)+j−d ₂=(k ₂−d ₂)+j−1≤(d ₂−d ₂)+j−1<j. Therefore $\deg _{G[K_{1}\cup K_{2}]}\beta <j$. See Fig. 3(c). If u lies on D ₁ then $\deg _{G[K_{1}\cup K_{2}]}\beta \leq (k_{2}-1)+k_{1}$. In this case k ₁<j−d ₂. Therefore $\deg _{G[K_{1}\cup K_{2}]}\beta <j$.

Subcase 2.3 (v∈K ₂): Since k ₂≤d ₂ and d ₂<j, we have k ₂<j. Hence this case does not occur. □

Lemma 5

Let C denote the cycle G(n;±1) in G(n;±{1,2,…,j}), 1≤j<⌊n/2⌋, n≥3. Let K be a segment on C induced by k consecutive vertices on C where k≤⌊n/2⌋. If K ₁ and K ₂ are disjoint segments induced by k ₁ and k ₂ consecutive vertices on C respectively such that k ₁+k ₂=k then |E(G[K ₁∪K ₂])|≤|E(G[K])|.

Proof

The proof is by induction on k. Suppose k=2. Then |E(G[K])|=1. If u and v are nonadjacent vertices on C such that d _C (u,v)≤j then |E(G[{u,v}])|=1 and if d _C (u,v)>j, then |E(G[{u,v}])|=0. Thus |E(G[{u,v}])|≤|E(G[K])|. Assume the result to be true for k−1 consecutive vertices. Consider k consecutive vertices on C, k≤⌊n/2⌋. If k≤j+1 then G[K] is the complete graph on k vertices and hence it contains the maximum number of edges. Suppose k>j+1. Let K ₁ and K ₂ be disjoint segments induced by k ₁ and k ₂ consecutive vertices on C respectively such that k ₁+k ₂=k. By Lemma 4, G[K ₁∪K ₂] contains an end vertex v in K ₁ or K ₂ of degree at most j. Without loss of generality, let v be an end vertex of K ₁ with $\deg _{G[K_{1}\cup K_{2}]}v\leq j$. Delete the vertex v from K ₁∪K ₂ to obtain $K_{1}^{\prime }\cup K_{2}$ with k−1 vertices. By induction hypothesis $\vert E(G[K_{1}^{\prime }\cup K_{2}])\vert \leq \vert E(G[K^{\prime }])\vert$ where K′ is induced by k−1 consecutive vertices on C. Thus, $\vert E(G[K_{1}\cup K_{2}])\vert =\vert E(G[K_{1}^{\prime }\cup \{v\}\cup K_{2}])\vert \leq \vert E(G[K_{1}^{\prime }\cup K_{2}])\vert +j\leq \vert E(G[K^{\prime }])\vert +j=\vert E(G[K])\vert$. □

Lemma 6

A set of k consecutive vertices of G(n;±1) induces a maximum subgraph of G(n;±S) on k vertices, k≤⌊n/2⌋, S={1,2,…,j}, 1≤j<⌊n/2⌋, n≥3.

Proof

Let the cycle G(n;±1) be denoted by C and let A be a set of k consecutive vertices on C. Let B be a set of k non-consecutive vertices on C. Then $B=\bigcup_{i=1}^{p}X_{i}$ where p≥2, X _i ’s are mutually disjoint and each X _i is a set of consecutive vertices on C such that $\sum_{i=1}^{p}\vert X_{i}\vert =k$. We claim that |E(G[B])|≤|E(G[A])|. We prove this claim by induction on p. When p=2, by Lemma 5, we get |E(G[B])|≤|E(G[A])|. Assume that the claim is true for p−1. Then $\vert E(G[ \bigcup_{i=1}^{p-1}X_{i}])\vert \leq \vert E(G[X])\vert$ where X is induced by k−|X _p | consecutive vertices on C. Now, $\vert E(G[ \bigcup_{i=1}^{p}X_{i}] )\vert =\vert E(G[ \bigcup_{i=1}^{p-1}X_{i}\cup X_{p}])\vert \leq \vert E(G[X\cup X_{p}])\vert \leq \vert E(G[A])\vert$. See Fig. 4.

Fig. 4

|X|=k−|X _p | and |A|=k

 □

The following result shows that Lemma 6 is true even if the restriction on the upper bound of k is relaxed.

Theorem 1

A set of k consecutive vertices of G(n;±1), 1≤k≤n induces a maximum subgraph of G(n;±S), where S={1,2,…,j}, 1≤j<⌊n/2⌋, n≥3.

Proof

By Lemma 6, a set of k≤⌊n/2⌋ consecutive vertices of G(n;±1) in G(n;±{1,2,…,j}) induces a maximum subgraph of G(n;±{1,2,…,j}). Since G(n;±{1,2,…,j}), 1≤j<⌊n/2⌋ is a regular graph, the remaining n−k vertices also induce a maximum subgraph of G. □

Theorem 2

The number of edges in a maximum subgraph on k vertices of G(n;±S), S={1,2,…,j}, 1≤j<⌊n/2⌋, 1≤k≤n, n≥3 is given by

$$\xi =\left\{\begin{array}{l@{\quad }l}k(k-1)/2 & k\leq j+1 \\kj-j(j+1)/2 & j+1<k\leq n-j \\\frac{1}{2}\{(n-k)^{2}+(4j+1)k-(2j+1)n\} & n-j<k\leq n.\end{array}\right.$$

Proof

Let K={v ₁,v ₂,…,v _k } be a set of k consecutive vertices of G(n;±1) in G(n;±S). By Theorem 1, G[K] is a maximum subgraph of G(n;±S) on k vertices.

Case 1 (k≤n−j): The number of edges induced by K in G(n;±i), 1≤i≤j is given by

$$\xi _{i}=\left\{\begin{array}{l@{\quad }l}k-i & k>i \\[3pt]0 & \text{otherwise.}\end{array}\right.$$

See Fig. 5. Therefore,

$$\vert E(G[{K}])\vert =\sum_{i=1}^{j}\xi _{i}=\sum_{i=1}^{\min \{j,k-1\}}(k-i).$$

This implies that

$$\xi =\left\{\begin{array}{l@{\quad }l}k(k-1)/2 & k\leq j+1 \\[2pt]kj-j(j+1)/2 & k>j+1.\end{array}\right.$$

Case 2 (k>n−j):

Fig. 5

Circulant graph (a) G(8;±1), (b) G(8;±2), (c) G(8;±3)

 □

4 Wirelength of circulant networks into arbitrary trees

A tree is a connected graph having no cycles. Any two vertices of a tree are joined by a unique path. The most common type of tree is the binary tree. It is so named because each node can have at most two descendents. A binary tree is said to be a complete binary tree if each internal node has exactly two descendents. These descendents are described as left and right children of the parent node. The binary search tree property (Cormen et al. 2001) of a binary tree states that all labels in the left subtree of any vertex x are all less than x, and all labels in the right subtree of x are greater than x. The consecutive label property is motivated by the binary search tree property (Rajasingh et al. 2004).

Definition 2

Let T be an ordered rooted tree with vertex labels 1,2,…,n. A subtree T′ of the tree T is consecutively labelled if the labels of T′ are consecutive numbers y+1,y+2,…,y+k where k denotes the number of vertices of T′.

Definition 3

Let T be an ordered rooted tree with vertex labels 1,2,…,n. A labeling of T satisfies the consecutive label property if for every vertex v of T, the subtrees T ₁,T ₂,…,T _m rooted at v are consecutively labeled.

Remark 2

Preorder, Inorder and Postorder labeling (Quadras 2005) of the vertices of trees induce consecutive label property in trees.

Embedding Algorithm A

Input: A circulant network G(n;±{1,2,…,j}), 1≤j<⌊n/2⌋ and an arbitrary rooted tree T on n vertices.

Algorithm: Label the consecutive vertices of G(n;±1) in G(n;±{1,2,…,j}) as 0,1,…,n−1 in the clockwise sense. Label the vertices of the tree as 0,1,…,n−1 using inorder labeling.

Output: An embedding f of G(n;±{1,2,…,j}) into T given by f(x)=x with minimum wirelength.

Proof of correctness: Let e be an edge of T. Then T−e yields a component T ₁ which is consecutively labeled (Rajasingh et al. 2004). By Theorem 1, the subgraph of G(n;±{1,2,…,j}) induced by {f ⁻¹(v):v∈T ₁} is maximum. By Congestion lemma, the congestion on e is minimum. This is true for every edge of T. Partition lemma implies that the wirelength is minimum.

The proof of the following result is an easy consequence of Lemma 2 and of the discussion in the proof of Theorem 2.

Theorem 3

The wirelength of G(n;±{1,2,…,j}),1≤j<⌊n/2⌋ into T is given by

$$\mathit{WL}(G(n;\pm \{1,2,\ldots,j\}),T)=2\sum_{e\in E(T)}\left\{jk(e)-\sum_{i=1}^{\min \{j,k(e)-1\}}\{k(e)-i\}\right\}$$

where k(e) is the number of vertices in the component T ₁ of T−e with k(e)≤⌊n/2⌋.

As G(n;±{1,2,…,⌊n/2⌋})≃K _n , we have the following result.

Theorem 4

The wirelength of the complete graph K _n into T is given by

$$\mathit{WL}(K_{n},T)=\sum_{e\in E(T)}k(e)\{n-k(e)\}$$

where k(e) is the number of vertices in the component T ₁ of T−e with k(e)≤⌊n/2⌋.

5 Wirelength of circulant networks into cycle related graphs

In this section we consider the embedding of circulant network into cycles and certain multicyclic graphs. Here C _n denotes a cycle on n vertices.

5.1 Even and odd cycles

Embedding Algorithm B

Input: A circulant network G(n;±{1,2,…,j}), 1≤j<⌊n/2⌋ and C _n .

Algorithm: Label the consecutive vertices of G(n;±1) in G(n;±{1,2,…,j}) and C _n as 0,1,…,n−1 in the clockwise sense.

Output: An embedding f of G(n;±{1,2,…,j}) into C _n given by f(x)=x with minimum wirelength.

Proof of correctness:

Case 1 (n even): Let the edge set E of C _n be partitioned into {S ₁,S ₂,…,S _n/2} where each S _i contains two diametrically opposite edges of C _n . In other words, S _i ={(i−1,i),(n/2+i−1,n/2+i)}, 1≤i≤n/2 where the labels are taken modulo n. See Fig. 6(a). For each i, E(C _n )∖S _i has two components H _i1 and H _i2. Let G _i1=f ⁻¹(H _i1) and G _i2=f ⁻¹(H _i2). Then each G _ij , j=1,2 is on n/2 consecutive vertices of G(n;±1). By Theorem 1, these vertices induce a maximum subgraph of G(n;±{1,2,…,j}), 1≤j<⌊n/2⌋. Thus each S _i satisfies conditions (i), (ii) and (iii) of the Congestion lemma. Therefore EC _f (S _i ) is minimum. Partition Lemma implies that the wirelength is minimum.

Fig. 6

(a) S _i  contains two diametrically opposite edges of C _n , n even (b) edge cuts of C ₅

Case 2 (n odd): For 1≤i≤2, let $S_{i}=\{S_{1}^{i},S_{2}^{i},\ldots,S_{(n-1)/2}^{i}\}$ where $S_{j}^{1}=\{( j-1,j) ,(\frac{n-3}{2}+j,\frac{n-1}{2}+j)\}$ and $S_{j}^{2}=\{( j-1,j) ,(\frac{n-1}{2}+j,\frac{n+1}{2}+j)\}$, 1≤j≤(n−1)/2, the labels taken modulo n. Let F ₁={(n−1,0)} and $F_{2}=\{(\frac{n-1}{2},\frac{n+1}{2})\}$. Then S _i partitions E(C _n )∖F _i , i=1,2. The sets F ₁,F ₂ are mutually disjoint and S=F ₁∪F ₂ is an edge cut of C _n . See Fig. 6(b). For each j, $E(C_{n})\setminus S_{j}^{i}$ has two components $H_{j1}^{i}$ and $H_{j2}^{i}$ induced by consecutive vertices on C _n with $\vert H_{j1}^{i}\vert =\lfloor n/2\rfloor$ and $\vert H_{j2}^{i}\vert =\lceil n/2\rceil$. Let $G_{j1}^{i}=f^{-1}(H_{j1}^{i})$ and $G_{j2}^{i}=f^{-1}(H_{j2}^{i})$. Then $G_{j1}^{i}$ is on ⌊n/2⌋ consecutive vertices of G(n;±1). By Theorem 1, these vertices induce a maximum subgraph of G(n;±{1,2,…,j}), 1≤j<⌊n/2⌋. Thus each $S_{j}^{i}$ satisfies conditions (i), (ii) and (iii) of the Congestion lemma. Therefore $\mathit{EC}_{f}(S_{j}^{i})$ is minimum. Similarly EC _f (S) is minimum. The Generalized Partition lemma (when k=2) implies that the wirelength is minimum.

Theorem 5

$\mathit{WL}(G(n;\pm \{1,2,\ldots,j\});1\leq j<\lfloor n/2\rfloor ,C_{n})=\frac{nj(j+1)}{2}$.

Proof

We have already proved that the embedding f defined in Embedding Algorithm B induces minimum wirelength of G(n;±{1,2,…,j}) onto C _n .

Case 1 (n even): Following the notation used in Case 1 of the algorithm, we have by Lemma 1, $\mathit{EC}_{f}(S_{1})=2j\lfloor n/2\rfloor -2\sum_{i=1}^{j}(\lfloor n/2\rfloor -i)=j(j+1)$. But C _n ∖S _i is isomorphic to C _n ∖S _j for i≠j. Therefore, $\mathit{WL}(G(n;\pm \{1,2,\ldots,j\}),C_{n})=\frac{n}{2}\mathit{EC}_{f}(S_{1})=\frac{nj(j+1)}{2}$.

Case 2 (n odd): Following the notation used in Case 2 of the algorithm, we have by Lemma 1, EC _f (S)=j(j+1). But C _n ∖S is isomorphic to $C_{n}\setminus S_{j}^{i}$ for 1≤i≤2, 1≤j≤(n−1)/2. Therefore, $\mathit{WL}(G(n;\pm \{1,2,\ldots,j\}),C_{n})=\frac{1}{2}\{\sum_{i=1}^{2}\sum_{j=1}^{(n-1)/2}\mathit{EC}_{f}(S_{j}^{i})+\mathit{EC}_{f}(S)\}=\frac{1}{2}\{(n-1)\mathit{EC}_{f}(S)+\mathit{EC}_{f}(S)\}=\frac{nj(j+1)}{2}$. □

Theorem 6

$\mathit{WL}(K_{n},C_{n})=\frac{n}{2}\lfloor n/2\rfloor \lceil n/2\rceil$.

5.2 Unicyclic graphs

A connected unicyclic graph arises from a tree by adding an extra edge. In other words, a graph which contains exactly one cycle C:v ₁ v ₂…v _m v ₁ is said to be a unicyclic graph, denoted by UC _m . Let T ₁,T ₂,…,T _m be trees with roots at v ₁,v ₂,…,v _m respectively. Then UC _m contains n vertices where n=|V(T ₁)|+|V(T ₂)|+⋯+|V(T _m )|.

Embedding Algorithm C

Input: A circulant network G(n;±{1,2,…,j}), 1≤j<⌊n/2⌋ and UC _m .

Algorithm: Label the consecutive vertices of G(n;±1) in G(n;±{1,2,…,j}) as 0,1,…,n−1 in the clockwise sense. Label the vertices of the unicyclic graph as follows: Label the vertex v ₁ as 0 and the vertices v _i+1, 1≤i≤m−1 as $\sum_{k=1}^{i}\vert V(T_{k})\vert$. Label the vertices of V(T ₁)╲v ₁ from 1 to |V(T ₁)|−1 and the vertices of V(T _i+1)╲v _i+1, 1≤i≤m−1 from $\sum_{k=1}^{i}\vert V(T_{k})\vert +1$ to $\sum_{k=1}^{i}\vert V(T_{k})\vert +\vert V(T_{i+1})\vert -1$ using inorder labeling.

Output: An embedding f of G(n;±{1,2,…,j}) into UC _m given by f(x)=x with minimum wirelength.

Proof of correctness: We partition the edges of each tree as in Sect. 4 and the edges of the cycle as in Sect. 5.1. A straightforward computation yields minimum wirelength.

5.3 Multicyclic graphs

A multicyclic graph is obtained from a tree by replacing at least two of the edges by two parallel edges and subdividing the parallel edges to obtain paths. The multicyclic graph can also be viewed as a particular class of series-parallel graphs. Series-parallel graphs are an important class of recursively defined graphs that can be characterized in many ways. The oldest and the most popular characterization due to Duffin (1965) provides a Kuratowski-like condition which states that a graph G is series-parallel if and only if it contains no subgraph homeomorphic to K ₄, the complete graph on four vertices.

A series–parallel graph is usually defined recursively by using parallel and series compositions. This classical definition justifies another name of these graphs, namely, 2-terminal series–parallel graphs, since we assume that every such graph has two nodes distinguished as poles and denoted by S (for South) and N (for North). A series–parallel graph G with poles S and N is defined as either

• (i) an edge (S,N)

or can be constructed as in (ii) or (iii):

• (ii) G is a parallel composition of at least two series-parallel graphs G ₁,G ₂,…,G _k (k≥2), denoted by G=G ₁∥G ₂∥…∥G _k . This operation identifies the South Poles S _i of the component graphs into the South Pole S of G, and similarly the North Poles N _i become N of G.

• (iii) G is a series composition of at least two series-parallel graphs G ₁,G ₂,…,G _l (l≥2), denoted by G=G ₁∘G ₂∘⋯∘G _l . This operation identifies N _i and S _i+1 for i=1,2,…,l−1, and assigns S ₁ to S and N _l to N.

Embedding Algorithm D

Input: A circulant graph G(l(n−1)+1;±{1,2,…,j}), $1\leq j<\lfloor \frac{l(n-1)+1}{2}\rfloor$ and a series-parallel graph H=G ₁∘G ₂∘⋯∘G _l where G _i ≃C _n ,1≤i≤l, n even and the south pole and the north pole of each G _i are diametrically opposite vertices of C _n .

Algorithm: Label the consecutive vertices of G(l(n−1)+1;±1) in G(l(n−1)+1;±{1,2,…,j}) as 0,1,…,l(n−1) in the clockwise sense. Label the vertices of the series-parallel graph as follows: Without loss of generality, we name north pole N as S _l+1. Label south poles S _i as $\frac{(i-1)n}{2}$, 1≤i≤l+1. For each G _i , there are two edge disjoint paths between the south pole and the north pole. For 1≤i≤l, the internal vertices of a path from S _i to S _i+1 are labeled consecutively from $\frac{(i-1)n}{2}+1$ to $\frac{in}{2}-1$ and the internal vertices of the other path from S _i to S _i+1 are labeled consecutively from $\frac{(2l-i+1)n}{2}-l+i-1$ to $\frac{(2l-i)n}{2}-l+i+1$.

Output: An embedding f of G(l(n−1)+1;±{1,2,…,j}), $1\leq j<\lfloor \frac{l(n-1)+1}{2}\rfloor$ into H=G ₁∘G ₂∘⋯∘G _l where G _i ≃C _n ,1≤i≤l, n even, given by f(x)=x with minimum wirelength.

Proof of correctness: As in the case of embedding circulant graph into an even cycle, let edge set E of the series-parallel graph H be partitioned into $\{S_{m}^{i}:1\leq i\leq l, 1\leq m\leq n/2\}$ where each $S_{m}^{i}$ contains two diametrically opposite edges of G _i , 1≤i≤l, in G ₁∘G ₂∘⋯∘G _l . See Fig. 7. For 1≤i≤l, 1≤m≤n/2, $E(H)\setminus S_{m}^{i}$ has two components $H_{m1}^{i}$ and $H_{m2}^{i}$ induced by consecutive vertices on H. Let $G_{m1}^{i}=f^{-1}(H_{m1}^{i})$ and $G_{m2}^{i}=f^{-1}(H_{m2}^{i})$. Then $G_{m1}^{i}$ is induced by consecutive vertices of G(l(n−1)+1;±{1,2,…,j}). Again by Lemmas 1 and 2, f induces minimum wirelength.

Fig. 7

$S_{1}^{i}$ and $S_{n/2}^{i}$ contain two diametrically opposite edges of G _i ≃C ₆, l=5, n=6

Theorem 7

The wirelength of G(l(n−1)+1;±{1,2,…,j}), $1\leq j<\lfloor \frac{l(n-1)+1}{2}\rfloor$ into H=G ₁∘G ₂∘⋯∘G _l where G _i ≃C _n ,1≤i≤l, n even, is given by

$$\mathit{WL}(G,H)=\left\{\begin{array}{l@{\quad }l}2n\sum_{i=1}^{l/2}\bigl\{ jx-\sum_{p=1}^{\min \{j,x-1\}}(x-p)\bigr\} & l\ \mathit{even}\\[6pt]2n\sum_{i=1}^{(l-1)/2}\bigl\{ jx-\sum_{p=1}^{\min \{j,x-1\}}(x-p)\bigr\} \\[6pt]\quad {}+n\bigl\{ jy-\sum_{p=1}^{\min \{j,y-1\}}(y-p)\bigr\} & l\ \mathit{odd}\end{array}\right.$$

where x=[2(i−1)(n−1)+n]/2 and y=[(l−1)(n−1)+n]/2.

Proof

Clearly, $H\setminus S_{m}^{i}$ is isomorphic to $H\setminus S_{m}^{(l-i+1)}$ for 1≤i≤⌊l/2⌋, 1≤m≤n/2. Therefore, $\mathit{EC}_{f}(S_{m}^{i})=\mathit{EC}_{f}(S_{m}^{(l-i+1)})$.

Case 1 (l even):

Case 2 (l odd):

where x=[2(i−1)(n−1)+n]/2 and y=[(l−1)(n−1)+n]/2. □

Remark 3

The techniques adopted in this Section allow us to compute the exact wirelength of circulant networks into all classes of multicyclic graphs.

6 Wirelength of circulant networks into ladders

In this section we consider the embedding of circulant network G(2n;±{1,2,…,j}), 1≤j<n into the ladder P ₂×P _n .

Embedding Algorithm E

Input: A circulant network G(2n;±{1,2,…,j}), 1≤j<n and the ladder P ₂×P _n .

Algorithm: Label the consecutive vertices of G(2n;±1) in G(2n;±{1,2,…,j}) as 0,1,…,2n−1 in the clockwise sense. Label the vertices of the ladder as follows: The first row is labeled 0 to n−1 from left to right and the second row is labeled n to 2n−1 from right to left.

Output: An embedding f of G(2n;±{1,2,…,j}) into P ₂×P _n given by f(x)=x with minimum wirelength.

Proof of correctness: Let X be a horizontal edge cut of the ladder such that X disconnects the ladder into two components R ₁ and R ₂ where V(R ₁)={0,1,…,n−1} and V(R ₂)={n,n+1,…,2n−1}. Let Y _i be a vertical edge cut of the ladder such that Y _i disconnects the ladder into two components C _i and $C_{i}^{\prime }$ where V(C _i )={0,1,…,i−1}∪{2n−i,2n−i+1,…,2n−1} and $V(C_{i}^{\prime })=V(P_{2}\times P_{n})\setminus V(C_{i})$. See Fig. 8. Let G ₁ and G ₂ be the inverse images of R ₁ and R ₂ under this labeling. The edge cut X satisfies the conditions (i) and (ii) of the Congestion lemma. Since G ₁ is on n consecutive vertices of G(2n;±1) in G(2n;±{1,2,…,j}), by Theorem 1, |E(G ₁)| is maximum satisfying the condition (iii) of the Congestion lemma. Thus by the Congestion lemma, EC _f (X) is minimum. Again let G _i and $G_{i}^{\prime }$ be the inverse images of C _i and $C_{i}^{\prime }$ under this labeling. The edge cut Y _i satisfies the conditions (i) and (ii) of the Congestion lemma. Also G _i is induced by 2i consecutive vertices of G(2n;±1) in G(2n;±{1,2,…,j}). Thus EC _f (Y _i ) is minimum for i=1,2,…,n−1. Hence by Partition lemma the wirelength is minimum.

Fig. 8

X is a horizontal edge cut and Y _i is a vertical edge cut

Theorem 8

The wirelength of G(2n;±{1,2,…,j}),1≤j<n into P ₂×P _n is given by

Proof

We have

$$\mathit{EC}_{f}(X)=2jn-2\sum_{i=1}^{j}(n-i)=j(j+1).$$

Case 1 (n odd): Clearly, EC _f (Y _i )=EC _f (Y _n−i ) for 1≤i≤(n−1)/2.

Therefore,

Thus,

Case 2 (n even): Clearly, EC _f (Y _i )=EC _f (Y _n−i ) for 1≤i≤n/2−1.

Therefore,

Thus,

 □

7 Conclusion

We obtain the exact wirelength of circulant networks into arbitrary trees, certain multicyclic graphs and ladders. All the embeddings constructed in this paper are simple, elegant and produce exact wirelengths. It would be an interesting line of research to solve the following problem.

Open Problem

To find the exact wirelength of circulant networks into grids.