Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
Authors:
- Guy EvenGEGuy Even
- Sudipto GuhaSGSudipto Guha
- Baruch SchieberBSBaruch Schieber
- 1 January 2002
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 32 (1) , 231-252
Abstract
We give improved approximations for two classical embedding problems: (i) minimizing the number of crossings in a drawing on the plane of a bounded degree graph; and (ii) minimizing the VLSI layout area of a graph of maximum degree four. These improved algorithms can be applied to improve a variety of VLSI layout problems. Our results are as follows. (i) We compute a drawing on the plane of a bounded degree graph in which the sum of the numbers of vertices and crossings is O(log 3 n )$ times the optimal minimum sum. This is a logarithmic factor improvement relative to the best known result. (ii) We compute a VLSI layout of a graph of maximum degree four in a square grid whose area is O(log 4 n )$ times the minimum layout area. This is an O(log 2 n ) improvement over the best known long-standing result.Keywords
This publication has 11 references indexed in Scilit:
- On Crossing Sets, Disjoint Sets, and PagenumberJournal of Algorithms, 2000
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- Fast Approximate Graph Partitioning AlgorithmsSIAM Journal on Computing, 1999
- Applications of the Crossing NumberAlgorithmica, 1996
- Planar separators and the Euclidean normLecture Notes in Computer Science, 1990
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984
- Crossing Number is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1983
- Universality considerations in VLSI circuitsIEEE Transactions on Computers, 1981
- Area-efficient graph layouts1980
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979