Advertisement
Published in:
2011 | OriginalPaper | Chapter
On the Crossing Number of Generalized Fat Trees
Authors : Bharati Rajan, Indra Rajasingh, P. Vasanthi Beulah
Published in: Informatics Engineering and Information Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.