Multilayer grid embeddings for VLSI

DOI10.1007/BF01759038MaRDI QIDQ916362zbMATH OpenFDO

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

Publication date 1991

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01759038

zbMATH Keywords

gridembeddingplanar graphsthicknessVLSI

Mathematics Subject Classification ID

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

Recommendations

• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Rectilinear Graphs and Their Embeddings
• scientific article; zbMATH DE number 139786
• scientific article; zbMATH DE number 1256778
• Universality considerations in VLSI circuits

Cites work

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

Cited in

(27)

• The 6-girth-thickness of the complete graph
• Geometric Thickness in a Grid of Linear Area
• Design techniques for multilayer simulation type embedding networks by means of first-order transformations
• Compact grid layouts of multi-level networks
• Universality considerations in VLSI circuits
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• The time complexity of oriented chromatic number for acyclic oriented connected subcubic subgraphs of grids
• A lower bound on the area of permutation layouts
• The 4-girth-thickness of the complete multipartite graph
• scientific article; zbMATH DE number 139786 (Why is no real title available?)
• Optimal three-dimensional orthogonal graph drawing in the general position model.
• Straight-line drawings of 1-planar graphs
• Drawings of graphs on surfaces with few crossings
• The thickness of amalgamations and Cartesian product of graphs
• Thickness of the subgroup intersection graph of a finite group
• The Local Queue Number of Graphs with Bounded Treewidth
• On \(k\)-planar crossing numbers
• Planar straight-line embedding of double-tree ccan architecture on a rectangular grid
• On graph thickness, geometric thickness, and separator theorems
• A note on Halton's conjecture
• Three ways to cover a graph
• A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
• Rectilinear Graphs and Their Embeddings
• Enumeration of labeled nonplanar pentacyclic blocks
• Asymptotic component densities in programmable gate arrays realizing all circuits of a given size
• Geometric thickness in a grid
• Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout

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

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