We prove lower and upper bounds on bisection width of transposition gr
aphs. This class of graphs contains several frequently studied interco
nnection networks including star graphs and hypercubes. In particular,
we prove that the bisection width of the complete transposition graph
is of order Theta(n.n!) which solves the open problem (R) 3.356 of Le
ighton's book [10] and determine an asymptotically exact value of bise
ction width of the star graph. The results have applications to VLSI l
ayouts, cutwidth and crossing numbers of transposition graphs. We also
study bandwidth of these graphs. (C) 1998 Elsevier Science B.V. All r
ights reserved.