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

DOI10.1016/0020-0190(86)90122-5MaRDI QIDQ1084869zbMATH OpenOpenAlexFDO

Authors Ferng-Ching Lin, Wei-Kuan Shih

Publication date 1986

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://ntur.lib.ntu.edu.tw/bitstream/246246/155684/1/03.pdf

zbMATH Keywords

graph layoutlong edgesVLSIwire area lower bound

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Symbolic computation and algebraic computation (68W30) Applications of graph theory to circuits and networks (94C15)

Review text

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.

Recommendations

• Layout of the cube-connected cycles without long wires
• On VLSI layouts of the star graph and related networks
• Layouts for the Shuffle-Exchange Graph Based on the Complex Plane Diagram
• On the area of hypercube layouts.
• An area-maximum edge length trade-off for VSLI layout

Cites work

• A framework for solving VLSI graph layout problems
• An asymptotically optimal layout for the shuffle-exchange graph
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• New lower bound techniques for VLSI
• Parallel Processing with the Perfect Shuffle

Cited in

(2)

• Layout of the cube-connected cycles without long wires
• Layouts for the Shuffle-Exchange Graph Based on the Complex Plane Diagram

This page was built for publication: Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1084869)