New lower bound techniques for VLSI

DOI10.1007/BF01744433zbMath0488.94048OpenAlexW2066782398MaRDI QIDQ3950484

Frank Thompson 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

zbMATH Keywords

parallel computationcrossing numbergraph embeddingvery large scale integrationseparatormesh of treesbisection widthlayout areatree of mesheswire lengthThompson grid modelarea-efficient chip layoutsmaximum edge lengthN-node planar graphwire area

Mathematics Subject Classification ID

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

Related Items

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Space Crossing Numbers ⋮ Crossing number, pair-crossing number, and expansion ⋮ Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs ⋮ Crossing numbers of random graphs ⋮ Feedback vertex sets in mesh-based networks ⋮ A compact layout for the three-dimensional tree of meshes ⋮ The crossing number of locally twisted cubes \(L T Q_n\) ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ From art and circuit design to geometry and combinatorics ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ An annotated review on graph drawing and its applications ⋮ Representing shared data on distributed-memory parallel computers ⋮ Multilayer grid embeddings for VLSI ⋮ A lower bound on the area of permutation layouts ⋮ String graphs and incomparability graphs ⋮ Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On the \(k\)-planar local crossing number ⋮ Parallel restructuring and evaluation of expressions ⋮ On the decay of crossing numbers ⋮ Applications of a New Separator Theorem for String Graphs ⋮ A bipartite strengthening of the crossing Lemma ⋮ Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ SIMULTANEOUS ARITHMETIC PROGRESSIONS ON ALGEBRAIC CURVES ⋮ Testing gap \(k\)-planarity is NP-complete ⋮ Crossing and Weighted Crossing Number of Near-Planar Graphs ⋮ A Bipartite Strengthening of the Crossing Lemma ⋮ On edges crossing few other edges in simple topological complete graphs ⋮ A survey of graphs with known or bounded crossing numbers ⋮ Complexities of layouts in three-dimensional VLSI circuits ⋮ Deterministic P-RAM simulation with constant redundancy ⋮ Extremal problems on triangle areas in two and three dimensions ⋮ An asymptotically optimal layout for the shuffle-exchange graph ⋮ Crossing lemma for the odd-crossing number ⋮ Which crossing number is it anyway? ⋮ A framework for solving VLSI graph layout problems ⋮ Separator-based graph embedding into multidimensional grids with small edge-congestion ⋮ An upper bound for the crossing number of augmented cubes ⋮ Shallow grates

Cites Work

• Unnamed Item
• Area-time optimal VLSI networks for multiplying matrices
• The VLSI Complexity of Sorting
• A model of computation for VLSI with related complexity results
• Universality considerations in VLSI circuits
• Applications of a Planar Separator Theorem
• Bounds to Complexities of Networks for Sorting and for Switching
• The crossing number of K5,n