New lower bound techniques for VLSI

DOI10.1007/BF01744433MaRDI QIDQ3950484zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3821102 (Why is no real title available?)
• A model of computation for VLSI with related complexity results
• Applications of a Planar Separator Theorem
• Area-time optimal VLSI networks for multiplying matrices
• Bounds to Complexities of Networks for Sorting and for Switching
• The VLSI Complexity of Sorting
• The crossing number of K5,n
• Universality considerations in VLSI circuits

Cited in

(44)

• A survey of graphs with known or bounded crossing numbers
• On the decay of crossing numbers
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• On the \(k\)-planar local crossing number
• 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
• A compact layout for the three-dimensional tree of meshes
• Non-crossing shortest paths lengths in planar graphs in linear time
• Separator-based graph embedding into multidimensional grids with small edge-congestion
• An annotated review on graph drawing and its applications
• 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
• Shallow grates
• Extremal problems on triangle areas in two and three dimensions
• Crossing lemma for the odd-crossing number
• Simultaneous arithmetic progressions on algebraic curves
• The Dirac-Goodman-Pollack conjecture
• A framework for solving VLSI graph layout problems
• Complexities of layouts in three-dimensional VLSI circuits
• Deterministic P-RAM simulation with constant redundancy
• Feedback vertex sets in mesh-based networks
• 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
• 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)