# Characterization of the Congestion Lemma on Layout Computation

Authors: Jia-Bao Liu; Arul Jeya Shalini; Micheal Arockiaraj; J. Nancy Delaila
Journal: Journal of Mathematics
 (2021)

---

## Abstract

An embedding of a guest networkGN into a host network HN is to find a suitable bijective function between the vertices of the guest and the host such that each link of GN is stretched to a path in HN. The layout measure is attained by counting the length of paths in HN corresponding to the links in GN and with a complexity of finding the best possible function overall graph embedding. This measure can be computed by summing the minimum congestions on each link of HN, called the congestion lemma. In the current study, we discuss and characterize the congestion lemma by considering the regularity and optimality of the guest network. The exact values of the layout are generally hard to find and were known for very restricted combinations of guest and host networks. In this series, we derive the correct layout measures of circulant networks by embedding them into the path- and cycle-of-complete graphs.


---

## Body

## 1. Introduction

Nowadays, there is an emerging demand for high-performance concurrent functional in different fields which can be successfully achieved through parallel processing techniques. The core of a parallel processing system is the interconnected network by which the system processors are connected. One of the important challenges in parallel processing techniques is how to allocate the subprocesses to the processors within the system in such a way that the total communication cost is minimized. This issue in parallel processing can be reduced to a graph embedding problem [1, 2]. For this purpose, the network topology is formulated as a simple graph, in which the vertex set denotes the system processors and the edge set denotes the links connecting them.In this paper, the collection of vertices and edges of a simple graph networkGN are, respectively, represented by VGN and EGN. A graph embedding of a guest network GN into a host network HN is a kind of vertex and edge labeling denoted by a 1−1 and onto mapping μ:VGN⟶VHN together with 1−1 mapping R:EGN⟶ℛHN such that Re is a μx to μy path in HN, where e=x,y and ℛHN contains the collection of routes or paths in HN [2, 3]. The congestion of an edge s of HN is measured by counting the routes in Ree∈EGN such that s is in the route Re and denoted by ECμs. In other words, ECμs=e∈EGN:s∈ERe. The layout/wire length [4, 5] of GN by embedding μ in HN is defined as(1)LμGN,HN=∑e∈EGNERe=∑s∈EHNECμs.LetD be any subset of EHN. If we represent ECμD=∑e∈DECμe, then LμGN,HN=∑i=1pECfFi, where EHN=F1,F2,…,Fp is a partition. For λ≥1, construct a set based on the edges of HN such that each edge in HN is duplicated λ-times. Such a set is denoted by EλHN. Then,(2)LμGN,HN=1λ∑s∈EHNECμs.Furthermore, ifEλHN=D1,D2,…,Dm, then LμGN,HN=1/λ∑i=1mECμDi. The correct layout of GN by embedding in HN is measured by(3)LGN,HN=minμLμGN,HN.The main objective of parallel computing is to execute embeddings with the correct layout, and we certainly fix the accompanying functionR such that each edge e of GN is to a shortest Re path under μ, see Figure 1. Apart from that, the important topological descriptor, Wiener index [6], which is used in the characterization of chemical compounds can be obtained through LKq,MS, where Kq is the complete graph and MS is the considered molecular structure.Figure 1
The correct layout of the embedding circulant network into path byμx=x.The minimum layout problem plays an important role in finding an optimal solution for very large-scale integration (VLSI) chips physical layout [2], minimizing time delay of simulations in parallel computer systems, computer aided designs, structural engineering, cloning and visual stimuli models, and parallel architecture [7, 8]. The computation of layout measure has been already studied in a variety of papers, see [9, 10] and the references cited therein, for more details. The present study continues the layout computation of circulant graphs into path- and cycle-of-complete graphs.


## 2. Congestion Lemma

The combinatorial isoperimetric problems have emerged with important applications in the fields of communication systems and computer and physical sciences related disciplines. Harper [11, 12] has discovered the primary significance of edge isoperimetric problem (EIP), and it has been categorized into two types as follows [13].Definition 1.
(EIP(1)). For a graph networkGN, if F⊆VGN, then ΘGNF=v,w∈EGN:v∈F&w∉F. Given a positive integer k, ΘGNk=minF⊆VGN,F=kΘGNF. Then, EIP(1) finds F⊆VGN and F=k such that ΘGNk=ΘGNF.Definition 2.
(EIP(2)). For a graph networkGN, if F⊆VGN, then IGNF=v,w∈EGN:v,w∈F. Given a positive integer k, IGNk=maxF⊆VGN,F=kIGNF. Then, EIP(2) finds F⊆VGN and F=k such that IGNk=IGNF.In such a case,F is identified as optimal set corresponding to the EIP.Lemma 1 (see [11]).
(i) For a graph networkGN, ΘGNVGN−F=ΘGNF for all F⊆VGN. (ii) If GN is an r-regular graph, ΘGNF+2IGNF=rF and, for any positive integer k, ΘGNk=rk−2IGNk.The minimum layout of the hypercube network by embedding in a grid structure is derived using congestion lemma [14]. The generalized version of the congestion lemma appeared in [15] and the modified version in [16]. Here, we present a more general result that exemplifies the regularity and the optimality on the guest network.In what follows, letGN and HN be two given networks and F⊆EHN. Suppose the removal of F from HN splits the network into m components, namely, HN1,HN2,…,HNm. A graph embedding μ of GN into HN is F-repulsive if, when we let GNj=GNμ−1HNj, 1≤j≤m, the following conditions hold:(i)
Ife∈EGNj, 1≤j≤m, then ERe∩F=0(ii)
Ife=v,w, such that v∈VGNj and w∈VGNk, for j<k, then ERe∩F=1Lemma 2.
LetF⊆EHN and μ be an F-repulsive graph embedding of GN into HN. We have ECμF=EGN−∑j=1mEGNj. Moreover, among all the graph embeddings of GN into HN, ECμF is minimum if and only if the value ∑j=1mEGNj is maximum among all partitions of VGN=∪j=1mWj with Wj=VGNj, j=1,2,…,m.Proof.
LetX=x,y∈EGN:x∈VGNj,y∈VGNkforj<k. Since any edge x,y in GN either belongs to one of GNj or x in GNj and y in GNk for some j and k, we obtain(4)EGN=∑j=1mEGNj+X.
We now easily computeECμF bearing the conditions of the F-repulsive embedding. By assumption (i), the contribution to ECμF from the edges of GNj, 1≤j≤m, is zero. By assumption (ii), every edge x,y of X increases ECμF by 1. Thus, ECμF=X=EGN−∑j=1mEGNj.
Assume thatECμF is minimum. Suppose we had a partition giving a larger value than ∑j=1mEGNj, and we could define an embedding β using this partition such that ECβF<ECμF, a contradiction. Conversely, let ECμF be not minimum. Suppose there exists a graph embedding γ such that ECγF<ECμF, and consequently, we can find a partition with a larger value than ∑j=1mEGNj, which is not possible because of the F-repulsive embedding under μ.Lemma 3.
LetF⊆EHN and μ be an F-repulsive graph embedding of GN into HN. Among all the graph embeddings of GN into HN, (a) ECμF is minimum if GNjs are optimal with respect to EIP(1) and ECμF=1/2∑j=1mΘGNmj, mj=VGNj, and (b) when GN is an r-regular network, ECμF is minimum if GNjs are optimal with respect to EIP(2) and ECμF=r/2VGN−∑j=1mEGNj.Proof.
We assume thatGNjs are optimal sets with respect to EIP(1). Such a case results in ∑j=1mΘGNmj is minimum. Hence, ECμF=1/2∑j=1mΘGNmj is minimum [15]. By extending the idea to EIP(2), we can easily derive the case of r-regular network by applying the simple fact 2EGN=rVGN.It is interesting as well as crucial to note that allGNjs are not optimal, yet imply that ECμF is minimum. Furthermore, when m=2, the above lemma is reduced to the modified congestion lemma [16], as in Case (a), and the congestion lemma [14], as in Case (b).


## 3. Layout Computation

The purpose of the section is to derive the layout of circulant networks into a few graph structures generated from the path and the cycle. We begin with the basic results on circulant networks [2, 17, 18].Definition 3.
(see [2]). A circulant network, denoted by CNq;±D, D⊆1,2,…,⌊q/2⌋, q≥3, is constructed from VCN=0,1,…,q−1 such that ECN=i,j:j−i≡dmodq,d∈±D.With the optimum fault tolerance and best routing functionality, the circulant network is considered an excellent network over the years on account of its applications in the areas of computer binary code designs and telecommunication network systems. Particularly, circulant network is a natural generalized form of the double loop network, and in addition, a matrix representation generates the circulant if all its rows are periodic rotations of the first one. From the construction of circulant networks, one can easily see thatCNq;±1 and CNq;±1,2,…,⌊q/2⌋ are, respectively, the cycle Cq and the complete graph Kq. In our study, we denote the cycle CNq;±1 as a peripheral cycle. From the symmetry of circulant network, we have that CNq;±1,2,…,l, 1≤l<⌊q/2⌋, is a regular network of degree 2l.Lemma 4 (see [19]).
A set ofm consecutive vertices of CNq;±1, 1≤m≤q, is an optimal set with respect to EIP(2) in Gq;±D, D=1,2,…,l, 1≤l<⌊q/2⌋.Lemma 5 (see [19]).
For a circulant networkCNq;±D, D=1,2,…,l and 1≤l<⌊q/2⌋, 1≤m≤q, we have(5)ICNm=mm−12;m≤l+1ml−ll+12;l+1<m≤q−l12q−m2+4l+1m−2l+1q;q−l<m≤q.Definition 4.
A path-of-complete graph is obtained by unifying a bone pathv1,v2,…,vm and m−1 complete graphs Kq1,Kq2,…,Kqm−1 such that the edge vi,vi+1, 1≤i≤m−1, of the bone path shares an edge of the complete graph Kqi. We denote it by PCm;q1,q2,…,qm−1. In an analogous way, we can define a cycle-of-complete graph by combining a bone cycle of length m and Kq1,Kq2,…,Kqm complete graphs. This graph is denoted by CCm;q1,q2,…,qm.Clearly, the number of vertices inPCm;q1,q2,…,qm−1 and CCm;q1,q2,…,qm are q1+q2+⋯+qm−1−m−2 and q1+q2+⋯+qm−m, respectively. The different cases of path- and cycle-of-complete graphs are shown in Figure 2. In the literature, these structures are sometimes called necklace graphs and also sharing between graphs by vertices, see [20, 21].Figure 2
Path-of-complete graphs. (a)PC7;36−times. (b) PC7;46−times. (c) Cycle-of-complete graph CC6;46−times.
(a)(b)(c)In what follows,q0=0 and qα=qα−m, α>m.Theorem 1.
The minimum layout of circulant networkGN=CNq;±1,2,…,l, 1≤l<⌊q/2⌋, into path-of-complete graph HN=PCm;q1,q2,…,qm−1 such that q=q1+q2+⋯+qm−1−m−2 is given by LGN,HN=mEG−∑i=1mIGq1+q2+⋯+qi−1−i+2+IGq−q1+q2+⋯+qi−i.Proof.
We begin with the embedding method ofGN and HN. Label the peripheral cycle vertices of GN as 0,1,…,q−1 and the bone path vertices vi, 1≤i≤m, of HN as q1+q2+⋯+qi−1−i+1 in such a way that label the vertices (except on the path) of ith complete graph Kqi, 1≤i≤m−1, from q1+q2+⋯+qi−1−i+2 to q1+q2+⋯+qi−i−1. We prove that the graph embedding μ of GN into HN defined by μw=w yields the minimum layout. For 1≤i≤m−1, let Si be the set of edges in the complete graph Kqi. Then, HN−Si reduced to qi components HN1,HN2,…,HNqi with VHN1=0,1,…,q1+q2+⋯+qi−1−i+1, 2≤j≤qi−1, VHNj=q1+q2+⋯+qi−1−i+j, and VHNqi=q1+q2+⋯+qi−i,q1+q2+⋯+qi−i+1,…,q−1. By Lemma 4, the induced subgraph by μ−1v:v∈VHNi on GN is an optimal set. We now conclude that μ is Si-repulsive embedding of GN into HN. By Lemma 3, ECμSi is minimum and ECμSi=EGN−IGNq1+q2+⋯+qi−1−i+2+IGNq−q1+q2+⋯+qi−i. Therefore, LGN,HN=∑i=1mECμSi=mEGN−∑i=1mIGNq1+q2+⋯+qi−1−i+2+IGNq−q1+q2+⋯+qi−i.Theorem 2.
The minimum layout of circulant networkGN=CNq;±1,2,…,l, 1≤l<⌊q/2⌋, into cycle-of-complete graph HN=CCm;q1,q2,…,qm such that q=q1+q2+⋯+qm−1−m−1 is given by(6)LGN,HN=m2EGN−∑i=1m/2IGNqi+1+⋯+qm/2+i−1−m/2+1+IGNqm/2+i+1+⋯+qi−1−m/2+1:meven12∑i=1mIGNqi+1+⋯+qm−1/2+i−1−m−3/2+1+IGNqm−1/2+i+1+⋯+qi−1−m−1/2+1:modd.Proof.
We first give the labeling ofGN into HN and followed by embedding algorithm. Label the peripheral cycle vertices of GN as 0,1,…,q−1 and the bone cycle vertices vi, 1≤i≤m, of HN as q1+q2+⋯+qi−1−i+1 along the vertices (except on the cycle) of ith complete graph Kqi, 1≤i≤m, from q1+q2+⋯+qi−1−i+2 to q1+q2+⋯+qi−i−1. Let μ be an embedding from GN into HN defined by μw=w.Case 1 (m even): for 1≤i≤m/2, let Si be the set of edges in the complete graphs Kqi and Kqm/2+i. Then, HN−Si reduced to qi+qm/2+i−2 number of components HNis in which qi+qm/2+i−4 components have cardinalities one each and the remaining components with qi+1+⋯+qm/2+i−1−m/2+1 and qm/2+i+1+⋯+qi−1−m/2+1 vertices. By Lemma 4, the induced subgraph by μ−1v:v∈VHNj on GN is an optimal set. Therefore, μ is Si-repulsive embedding of GN into HN. By Lemma 3, ECμSi is minimum and ECμSi=EGN−IGNqi+1+⋯+qm/2+i−1−m/2+1+IGNqm/2+i+1+⋯+qi−1−m/2+1. By the construction of the edge cuts, we infer that Si:1≤i≤m/2 is a partition of EHN, and hence, LGN,HN=∑i=1m/2ECμSi=m/2EGN−∑i=1m/2IGNqi+1+⋯+qm/2+i−1−m/2+1+IGNqm/2+i+1+⋯+qi−1−m/2+1.Case 2 (m odd): for 1≤i≤m, let Si be the set of edges in the complete graphs Kqi and Kqm−1/2+i. Then, HN−Si reduced to qi+qm−1/2+i−2 number of components HNjs in which qi+qm−1/2+i−4 components have cardinalities one each and the remaining components with qi+1+⋯+qm−1/2+i−1−m−3/2+1 and qm−1/2+i+1+⋯+qi−1−m−1/2+1 vertices. By Lemma 4, the induced subgraph by μ−1v:v∈VHNj is an optimal set. Therefore, μ is Si-repulsive embedding of GN into HN. By Lemma 3, ECμSi is minimum and ECμSi=EGN−IGNqi+1+⋯+qm−1/2+i−1−m−3/2+1+IGNqm−1/2+i+1+⋯+qi−1−m−1/2+1. We note that Si:1≤i≤m is a partition of E2HN, and hence, LGN,HN=1/2∑i=1mECμSi=m/2EGN−1/2∑i=1mIGNqi+1+⋯+qm−1/2+i−1−m−3/2+1+IGNqm−1/2+i+1+⋯+qi−1−m−1/2+1.


## 4. Conclusion

In analyzing the structural properties of a connected network, the measure such as graph embedding is of greater interest. As we know that the path, cycle, complete, and circulant graphs are important interconnection networks due to their simplicity, in this article, we successfully embedded circulant graphs into path- and cycle-of-complete graphs with minimum layout by the way of characterizing the congestion lemma with respect to regularity and optimality on the guest network.



---

*Source: 2984703-2021-10-27.xml*