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 -