A Framework for Solving VLSI Graph Layout Problems

This paper introduces a new divide-and-conquer framework for VLSI graph layout. Universally close upper and lower bounds are obtained for important cost functions such as layout area and propagation delay. The framework is also effectively used to design regular and configurable layouts, to assemble large networks of processor using restructurable chips, and to configure networks around faulty processors. It is also shown how good graph partitioning heuristics may be used to develop provably good layout strategy.

• Publication year

  1983

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  1983-10-01

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1016/0022-0000(84)90071-0
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Wafer-Scale Integration of Systolic Arrays

  1985cited by this paper
• Three-Dimensional Circuit Layouts

  1984cited by this paper
• How to assemble tree machines

  1984cited by this paper
• Computational Aspects of VLSI

  1984cited by this paper
• Area and Delay Penalties in Restructurable Wafer-Scale Arrays

  1983cited by this paper
• ON BISECTING RANDOM GRAPHS

  1983cited by this paper
• Complexity Issues in VLSI

  1983cited by this paper
• Efficient VLSI Networks for Parallel Processing Based on Orthogonal Trees

  1983cited by this paper
• Area-Efficient VLSI Computation

  1983cited by this paper
• On driving many long lines in a VLSI layout

  1982cited by this paper
• LAYOUT FOR THE SHUFFLE-EXCHANGE GRAPH AND LOWER BOUND TECHNIQUES FOR VLSI

  1982cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• The "PI" (Placement And Interconnect) System

  1982cited by this paper
• New lower bound techniques for VLSI

  1981cited by this paper
• Minimum Edge Length Planar Embeddings of Trees

  1981cited by this paper
• Universality considerations in VLSI circuits

  1981cited by this paper
• Bounds on minimax edge length for complete binary trees

  1981cited by this paper
• Graph separator theorems and sparse Gaussian elimination

  1980cited by this paper
• A Complexity Theory for VLSI

  1980cited by this paper
• The compilation of regular expressions into integrated circuits

  1980cited by this paper
• Area-time complexity for VLSI

  1979cited by this paper
• Systolic Priority Queues

  1979cited by this paper
• Introduction to VLSI systems

  1978cited by this paper
• An efficient heuristic cluster algorithm for tearing large-scale networks

  1977cited by this paper
• A Separator Theorem for Planar Graphs

  1977cited by this paper
• On non-linear lower bounds in computational complexity

  1975cited by this paper
• An efficient heuristic procedure for partitioning graphs

  1970cited by this paper
• Memory bounds for recognition of context-free and context-sensitive languages

  1965cited by this paper

• GLaDOS: Graph Layout algorithm Datasets for Open Science

  2026cites this paper
• Reinforcement learning driven heuristic for two-dimensional bandwidth minimization

  2025cites this paper
• Optimizing the layout of embedding BCube into grid architectures

  2025cites this paper
• A New Infinite Family of $4$-regular Crossing-critical Graphs

  2025cites this paper
• Generalizations of the Crossing Lemma

  2025cites this paper
• An Ant Colony Optimization approach to solving the Vertex Separator Problem

  2025cites this paper
• A Novel Local Search Algorithm for the Vertex Bisection Minimization Problem

  2025cites this paper
• Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry

  2025cites this paper
• Non-crossing shortest paths lengths in planar graphs in linear time

  2024cites this paper
• A fast path relinking algorithm for the min-max edge crossing problem

  2024cites this paper
• An Algorithm for Estimating the Crossing Number of Dense Graphs, and Continuous Analogs of the Crossing and Rectilinear Crossing Numbers

  2024cites this paper
• Rectilinear Crossing Number of Graphs Excluding a Single-Crossing Graph as a Minor

  2024cites this paper
• Generative Modelling of Structurally Constrained Graphs

  2024cites this paper
• Rectilinear Crossing Number of Graphs Excluding Single-Crossing Graphs as Minors

  2024cites this paper
• Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra

  2024cites this paper
• Hypergraph universality via branching random walks

  2024cites this paper
• A Two-Phase Heuristic Algorithm for Effective Graph Partitioning

  2024cites this paper
• A new infinite family of 4-regular crossing-critical graphs

  2024cites this paper
• Direct Product Multicommodity Max-Concurrent-Flow Min-Sparse-Cut Theorem

  2024cites this paper
• On Approximating Cutwidth and Pathwidth

  2023cites this paper
• Skewness and the crossing numbers of graphs

  2023cites this paper
• Clock Distribution with Gradient TRIX

  2023cites this paper
• Stochastic embeddings of graphs into trees

  2023cites this paper
• Ortho-Radial Drawing in Near-Linear Time

  2023cites this paper
• PlanE: Representation Learning over Planar Graphs

  2023cites this paper
• A Reduced Variable Neighbourhood Search Algorithm for Grid Bandwidth Minimization Problem

  2023cites this paper
• Universality for graphs with bounded density

  2023cites this paper
• Convexity Hierarchies in Grid Networks

  2023cites this paper
• Pair Crossing Number, Cutwidth, and Good Drawings on Arbitrary Point Sets

  2022influential citation
• Efficient iterated greedy for the two-dimensional bandwidth minimization problem

  2022cites this paper
• Clustering Driven Iterated Hybrid Search for Vertex Bisection Minimization

  2022cites this paper
• A general variable neighborhood search for the cyclic antibandwidth problem

  2022cites this paper
• Non-Crossing Shortest Paths are Covered with Exactly Four Forests

  2022cites this paper
• A note on the SDP relaxation of the minimum cut problem

  2022cites this paper
• Efficient Splitting of Necklaces

  2021cites this paper
• A Topology-Shape-Metrics Framework for Ortho-Radial Graph Drawing

  2021cites this paper
• Graph Embedding

  2021cites this paper
• Improved Scalability of Demand-Aware Datacenter Topologies With Minimal Route Lengths and Congestion

  2021cites this paper
• Non-crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time

  2021cites this paper
• Characterization of the Congestion Lemma on Layout Computation

  2021cites this paper
• Fair Partitions

  2021cites this paper
• Embedding algorithm of spined cube into grid structure and its wirelength computation

  2021cites this paper
• Search Trajectory Networks Applied to the Cyclic Bandwidth Sum Problem

  2021cites this paper
• A variable depth neighborhood search algorithm for the Min-Max Arc Crossing Problem

  2021cites this paper
• A Note on the Crossing Number of the Cone of a Graph

  2021cites this paper
• It's Good to Relax: Fast Profit Approximation for Virtual Networks with Latency Constraints

  2021cites this paper
• Artificial Evolution: 14th International Conference, Évolution Artificielle, EA 2019, Mulhouse, France, October 29–30, 2019, Revised Selected Papers

  2020cites this paper
• Rotation and Crossing Numbers for Join Products

  2020cites this paper
• Tabu search for min-max edge crossing in graphs

  2020cites this paper
• Relating the bisection width of dual-port, server-centric datacenter networks and the solution of edge isoperimetric problems in graphs

  2020cites this paper
• Non-crossing Shortest Paths Lengths in Planar Graphs in Linear Time

  2020cites this paper
• The Crossing Number of Circulant Graph C(3k+1;{1,k}) on the Projective Plane

  2020cites this paper
• Rotation and Crossing Numbers for Join Products

  2020cites this paper
• Computing Lengths of Shortest Non-Crossing Paths in Planar Graphs

  2020cites this paper
• A new iterated local search algorithm for the cyclic bandwidth problem

  2020cites this paper
• Towards Better Approximation of Graph Crossing Number

  2020cites this paper
• FISSION: A Practical Algorithm for Computing Minimum Balanced Node Separators

  2020cites this paper
• Hypergraph partitioning using tensor eigenvalue decomposition

  2020cites this paper
• Efficient Splitting of Measures and Necklaces

  2020influential citation
• New hardness results for planar graph problems in p and an algorithm for sparsest cut

  2020cites this paper
• Embedding Augmented Cubes into Grid Networks for Minimum Wirelength

  2020cites this paper
• A linear time algorithm for embedding locally twisted cube into grid network to optimize the layout

  2020cites this paper
• Width of Graph Mappings

  2020cites this paper
• A Study of Recombination Operators for the Cyclic Bandwidth Problem

  2019cites this paper
• Brain Storm Optimization Algorithms for Solving Equations Systems

  2019cites this paper
• Scalable Graph Algorithms

  2019cites this paper
• Efficient Algorithms for Ortho-Radial Graph Drawing

  2019cites this paper
• An Iterated Three-Phase Search Approach for Solving the Cyclic Bandwidth Problem

  2019cites this paper
• Facial Reduction for Symmetry Reduced Semidefinite Programs

  2019cites this paper
• Heuristics for the Constrained Incremental Graph Drawing Problem

  2019cites this paper
• Wirelength of Enhanced Hypercube into Windmill and Necklace Graphs

  2019cites this paper
• Exact Crossing Number Parameterized by Vertex Cover

  2019cites this paper
• Alternative evaluation functions for the cyclic bandwidth sum problem

  2019cites this paper
• Cellular processing algorithm for the vertex bisection problem: Detailed analysis and new component design

  2019cites this paper
• Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs

  2019cites this paper
• Comparative Study of Different Memetic Algorithm Configurations for the Cyclic Bandwidth Sum Problem

  2018cites this paper
• PR ] 22 M ay 2 01 8 Optimal Cheeger cuts and bisections of random geometric graphs

  2018cites this paper
• Heuristics for the min-max arc crossing problem in graphs

  2018cites this paper
• The min-cut and vertex separator problem

  2018cites this paper
• Tight Upper Bounds on the Crossing Number in a Minor-Closed Class

  2018cites this paper
• Logic learning and optimized drawing: two hard combinatorial problems

  2018cites this paper
• Balanced tree partition problems with virtual nodes

  2018cites this paper
• Layout model for optical interconnects based on λ-routing grids and topology embeddings

  2018cites this paper
• The crossing number of locally twisted cubes LTQn

  2018cites this paper
• Optimal Cheeger cuts and bisections of random geometric graphs

  2018cites this paper
• The min-cut and vertex separator problem

  2017cites this paper
• Distributed evolutionary k-way node separators

  2017cites this paper
• Bandwidths Optimization on Sparse Matrices Using Brain Storm Optimization

  2017cites this paper
• A hybrid breakout local search and reinforcement learning approach to the vertex separator problem

  2017cites this paper
• Optimal Embedding of Locally Twisted Cubes into Grids

  2017cites this paper
• The S-labeling problem: An algorithmic tour

  2017cites this paper
• New Abilities and Limitations of Spectral Graph Bisection

  2017cites this paper
• Rectilinear Crossing Minimization Master Thesis of Klara Reichard

  2017cites this paper
• The Complexity of Tree Partitioning

  2017cites this paper
• Algorithms and Discrete Applied Mathematics - Third International Conference, CALDAM 2017, Sancoale, Goa, India, February 16-18, 2017, Proceedings

  2017cites this paper
• On the Minimum Bisection Problem in Tree-Like and Planar Graphs

  2017cites this paper
• 32nd International Symposium on Computational Geometry, SoCG 2016, Boston, MA, USA, June 14-18, 2016

  2016cites this paper
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem

  2016cites this paper
• Impact of Parallelism and Memory Architecture on FPGA Communication Energy

  2016cites this paper
• Energy Reduction Through Voltage Scaling and Lightweight Checking

  2016cites this paper