Header menu link for other important links
X
On the crossing number of generalized fat trees
B. Rajan, , P. Vasanthi Beulah
Published in
2011
Volume: 253 CCIS
   
Issue: PART 3
Pages: 440 - 448
Abstract
The crossing number of a graph G is the minimum number of crossings of its edges among the drawings of G in the plane and is denoted by cr(G). Bhatt and Leighton proved that the crossing number of a network is closely related to the minimum layout area required for the implementation of the VLSI circuit for that network. In this paper, we find an upper bound for the crossing number of a special case of the generalized fat tree based on the underlying graph model found in the literature. We also improve this bound for a new drawing of the same structure. The proofs are based on the drawing rules introduced in this paper. © 2011 Springer-Verlag.
About the journal
JournalCommunications in Computer and Information Science
ISSN18650929