The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                            Computer Science Seminar

                                    Guy Even
                        Electrical Engineering - Systems
                              Tel-Aviv University


                                 will speak on


                      Improved Approximations of Crossings
                    in Graph Drawings and VLSI Layout Areas

Abstract:
We give improved approximations for two classical embedding problems.  First,
we compute drawings of bounded degree graphs on the plane in which the sum of
the number of vertices and the number of crossings is $O(\log^3 n)$ times the
minimum.  This is an improvement of a logarithmic factor relative to the best
known result (Bhatt-Leighton and Leighton-Rao). This has consequences in a
variety of VLSI layout problems.  Second, we compute a VLSI layout of a graph
of degree $4$ in a grid of constant aspect ratio. The area of the layout is
$O(\log^4 n)$ times the minimum layout area.  This is an $O(\log^2 n)$
improvement over Bhatt-Leighton and Leighton-Rao.

Joint work with Sudipto Guha and Baruch Schieber.





                      The lecture will take place in the 
                     Lecture Hall, Room 1, Ziskind Building
                            on Monday, March 27, 2000
                                    at 14:30