TY - GEN

T1 - Improved approximations of crossings in graph drawings

AU - Even, Guy

AU - Guha, Sudipto

AU - Schieber, Baruch

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84878913592&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84878913592&partnerID=8YFLogxK

U2 - 10.1145/335305.335340

DO - 10.1145/335305.335340

M3 - Conference contribution

AN - SCOPUS:84878913592

SN - 1581131844

SN - 9781581131840

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 296

EP - 305

BT - Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000

T2 - 32nd Annual ACM Symposium on Theory of Computing, STOC 2000

Y2 - 21 May 2000 through 23 May 2000

ER -