On the crossing numbers of loop networks and generalized Petersen graphs
Conference Paper

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

Bhatt and Leighton proved that the crossing number of a network (graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the crossing numbers of graphs with good interconnection properties, such as the circulant graphs G(n;±s1,...,±sm). In this work we find tight bounds for the crossing numbers of the (double fixed step) circulant graphs G(n;±1,±k). Specifically, we show that for values of n sufficiently large compared to k, the crossing number of G(n;±1,±k) is bounded by above and by below by linear functions of n, both of which have coefficients that approach 1 as k goes to infinity. As an additional application of these bounds, we show that the crossing numbers of the generalized Petersen graphs P(n,k) are bounded by below and by above by linear functions of n, whose coefficients approach 25 and 2, respectively, as k goes to infinity. © 2005 Published by Elsevier B.V.
publication date
published in
Research
keywords

Circulant; Crossing numbers; Generalized Petersen graphs; Interconnection networks; Loop networks; VLSI layout Functions; Integrated circuit layout; Interconnection networks; Linear systems; VLSI circuits; Circulants; Crossing numbers; Generalized Petersen graphs; Loop networks; VLSI layout; Graph theory
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue