LONG EDGES IN THE LAYOUTS OF SHUFFLE-EXCHANGE AND CUBE-CONNECTED CYCLES GRAPHS

[[abstract]]A direct method is devised to prove, without information-theoretic arguments, the OMEGA (N**2/log**2N) wire area lower bound for the shuffle-exchange and cube-connected cycles graphs. We further show the high occurrence of long edges in two ways: (1) In any layout, there are OMEGA (N/log N) edges whose lengths are at least N/32 log**2N. (2) The edges whose lengths are at least N/64log**2N occupy OMEGA (N**2/log**2N) wire area.[[fileno]]2030218010009[[department]]資訊工程學