Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
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.
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
Liat Ein-Dor, Y. Goldschmidt, et al.
IBM J. Res. Dev
M.J. Slattery, Joan L. Mitchell
IBM J. Res. Dev
Rajiv Ramaswami, Kumar N. Sivarajan
IEEE/ACM Transactions on Networking