Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
On the Crossing Number of Generalized Fat Trees
verfasst von : Bharati Rajan, Indra Rajasingh, P. Vasanthi Beulah
Erschienen in: Informatics Engineering and Information Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.