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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs
scientific article

    Statements

    Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs (English)
    0 references
    0 references
    0 references
    1986
    0 references
    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.
    0 references
    graph layout
    0 references
    VLSI
    0 references
    wire area lower bound
    0 references
    long edges
    0 references

    Identifiers