The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                            Computer Science Seminar

                                Yuri Rabinovich
                                Haifa  University


                                 will speak on


                          $L_1$  EMBEDDINGS OF GRAPHS 

Abstract:
We shall discuss the present state of the following intriguing conjecture:

Is it true that the shortest-path metric of any planar graph can be embedded
into $L_1$ with a constant distortion?

Or, equivalently,

Is it true that for multicommodity flows on planar networks, the gap between
the MinCut and the MaxFlow is at most constant?


The older related findings include, e.g., the Okamura-Seymour's Theorem
implying that any disc metric is isometrically embeddable into $L_1$, and
Seymour's Theorem implying that the restriction of the shortest path metric of
a weighted planar graph $G$ to its set of edges $E(G)$ can be extended to an
$L_1$ embeddable metric on $V(G)$. Another related result, due to
Klein-Plotkin-Rao claims, in the language of metrics, that for a planar graph
$G$ it always holds:

 EdgeExpansion(G) x AverageDistance(G) = O(1).


The more recent results include Rao's proof that a metric of a weighted planar
graph can be embedded into $L_2$(and hence $L_1$) with distortion at most
$O(\sqrt{\log\ n})$, and [GNSR] proof of the conjecture for $K_4$-free graphs.





                      The lecture will take place in the 
                    Seminar Room, Room 1, Ziskind Building
                            on Monday, May 8, 2000
                                    at 14:30