Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs (Q1084869)

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/64 log\({}^ 2N\) occupy \(\Omega (N^ 2/\log^ 2N)\) wire area.