Many Distances in Planar Graphs |
| |
| Authors: | Sergio Cabello |
| |
| Affiliation: | 1. Department of Mathematics, Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia
2. Department of Mathematics, Institute for Mathematics, Physics and Mechanics, Ljubljana, Slovenia
|
| |
| Abstract: | We show how to compute in O(n 4/3log?1/3 n+n 2/3 k 2/3log?n) time the distance between k given pairs of vertices of a planar graph G with n vertices. This improves previous results whenever (n/log?n)5/6≤k≤n 2/log?6 n. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
