Multilayer grid embeddings for VLSI

DOI10.1007/BF01759038zbMath0703.68044MaRDI QIDQ916362

Alok Aggarwal, Peter W. Shor, Maria M. Klawe

Publication date: 1991

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

embeddingthicknessplanar graphsVLSIgrid

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Circuits, networks (94C99)

Related Items (max. 100)

Optimal three-dimensional orthogonal graph drawing in the general position model. ⋮ The thickness of amalgamations and Cartesian product of graphs ⋮ Thickness of the subgroup intersection graph of a finite group ⋮ Drawings of graphs on surfaces with few crossings ⋮ A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid ⋮ On \(k\)-planar crossing numbers ⋮ Straight-line drawings of 1-planar graphs ⋮ On graph thickness, geometric thickness, and separator theorems ⋮ Three ways to cover a graph ⋮ Geometric thickness in a grid ⋮ A lower bound on the area of permutation layouts ⋮ Asymptotic component densities in programmable gate arrays realizing all circuits of a given size ⋮ A note on Halton's conjecture ⋮ The 6-girth-thickness of the complete graph ⋮ The 4-girth-thickness of the complete multipartite graph ⋮ The Local Queue Number of Graphs with Bounded Treewidth ⋮ Geometric Thickness in a Grid of Linear Area

Cites Work

• Unnamed Item
• A lower bound on the area of permutation layouts
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Algorithms for drawing graphs: An annotated bibliography
• On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
• Universal Chains and Wiring Layouts
• A Separator Theorem for Planar Graphs
• Universality considerations in VLSI circuits
• Applications of a Planar Separator Theorem
• New lower bound techniques for VLSI
• Double-row planar routing and permutation layout
• Determining the thickness of graphs is NP-hard
• Thickness of graphs with degree constrained vertices
• The multilayer routing problem: Algorithms and necessary and sufficient conditions for the single-row, single-layer case
• Permutation layout
• On optimum single-row routing

This page was built for publication: Multilayer grid embeddings for VLSI