Improved approximations of crossings in graph drawings and VLSI layout areas

Guy Even, Sudipto Guha, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

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(log3 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(log4 n) times the minimum layout area. This is an O(log2 n) improvement over the best known long-standing result.

Original languageEnglish (US)
Pages (from-to)231-252
Number of pages22
JournalSIAM Journal on Computing
Volume32
Issue number1
DOIs
StatePublished - Jan 1 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Approximation algorithm
  • Crossing number
  • Graph drawing
  • VLSI layout

Fingerprint Dive into the research topics of 'Improved approximations of crossings in graph drawings and VLSI layout areas'. Together they form a unique fingerprint.

Cite this