| DATE: | Wednesday, September 22nd 2004. |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnel 320 |
| TITLE: | Counting maximum dilation pairs in planar graphs |
| SPEAKER: | Christian Knauer, Department of Mathematics and Computer Science, Freie Universitaet Berlin |
Let $P$ be a connected plane embedded graph on $n$ vertices. The {\em
dilation} of $P$ on two vertices,
$x$ and $y$, is defined to be the Euclidean length of the shortest path
in
$P$ that connects $x$ with $y$, divided by
their Euclidean distance. We are interested in counting the number of
vertex
pairs that attain the maximum dilation on $P$.
For paths we describe an $O(n^{3/2} \log n)$ algorithm for counting the
number of maximum dilation pairs. Then we briefly sketch how to
generalize
this result to closed curves and trees. This joint work with Giri
Narasimhan, Rolf Klein, and Michiel Smid.