True 3-D displays for avionics and mission crewstations
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997
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.
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
G. Ramalingam
Theoretical Computer Science
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009