Improved approximations of crossings in graph drawings

Guy Even, Sudipto Guha, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

We give improved approximations for two classical embedding problems: (i) minimizing the number of crossings in a drawing of a bounded degree graph on the plane; and (ii) minimizing the VLSI layout area of a degree four graph. 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 degree four graph in a grid with constant aspect ratio the area of which is O(log4 n) times the optimal minimum layout area. This is an O(log2 n) improvement over the best known long standing result.

Original languageEnglish (US)
Title of host publicationProceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Pages296-305
Number of pages10
DOIs
StatePublished - Dec 1 2000
Externally publishedYes
Event32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, United States
Duration: May 21 2000May 23 2000

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Country/TerritoryUnited States
CityPortland, OR
Period5/21/005/23/00

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

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

Cite this