McGill University - School of Computer Science

Algorithms Seminar 2004

Everybody is welcome!

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at