New lower bound techniques for VLSI
DOI10.1007/BF01744433zbMATH Open0488.94048OpenAlexW2066782398MaRDI QIDQ3950484FDOQ3950484
Authors: F. Thomson Leighton 
Publication date: 1984
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01744433
parallel computationgraph embeddingcrossing numberseparatormesh of treesbisection widthvery large scale integrationlayout areatree of mesheswire lengthThompson grid modelarea-efficient chip layoutsmaximum edge lengthN-node planar graphwire area
Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)
Cites Work
- Applications of a Planar Separator Theorem
- Universality considerations in VLSI circuits
- The crossing number of K5,n
- Area-time optimal VLSI networks for multiplying matrices
- Bounds to Complexities of Networks for Sorting and for Switching
- The VLSI Complexity of Sorting
- A model of computation for VLSI with related complexity results
- Title not available (Why is that?)
Cited In (44)
- On the decay of crossing numbers
- On the \(k\)-planar local crossing number
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
- A bipartite strengthening of the crossing Lemma
- An asymptotically optimal layout for the shuffle-exchange graph
- Non-crossing shortest paths lengths in planar graphs in linear time
- A compact layout for the three-dimensional tree of meshes
- An annotated review on graph drawing and its applications
- Separator-based graph embedding into multidimensional grids with small edge-congestion
- String graphs and incomparability graphs
- Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization
- A lower bound on the area of permutation layouts
- Graph theory (algorithmic, algebraic, and metric problems)
- Testing gap \(k\)-planarity is NP-complete
- Which crossing number is it anyway?
- Crossing number, pair-crossing number, and expansion
- A Bipartite Strengthening of the Crossing Lemma
- From art and circuit design to geometry and combinatorics
- Applications of a new separator theorem for string graphs
- The Dirac-Goodman-Pollack conjecture
- Simultaneous arithmetic progressions on algebraic curves
- Shallow grates
- Crossing lemma for the odd-crossing number
- Extremal problems on triangle areas in two and three dimensions
- Feedback vertex sets in mesh-based networks
- A framework for solving VLSI graph layout problems
- Complexities of layouts in three-dimensional VLSI circuits
- Deterministic P-RAM simulation with constant redundancy
- The crossing number of locally twisted cubes \(L T Q_n\)
- Multilayer grid embeddings for VLSI
- Space crossing numbers
- Parallel restructuring and evaluation of expressions
- On edges crossing few other edges in simple topological complete graphs
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Crossing and Weighted Crossing Number of Near-Planar Graphs
- Representing shared data on distributed-memory parallel computers
- Non-crossing shortest paths lengths in planar graphs in linear time
- An upper bound for the crossing number of augmented cubes
- Crossing numbers of random graphs
- The crossing number of Cartesian product of sunlet graph with path and complete bipartite graph
- Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs
- A survey of graphs with known or bounded crossing numbers
- Representations of graphs and networks (coding, layouts and embeddings)
This page was built for publication: New lower bound techniques for VLSI
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3950484)
