Many distances in planar graphsCabello, Sergio (Avtor) matematikateorija grafovravninski grafrazdaljamathematicsgraph theoryplanar graphdistanceWe show how to compute in ▫$O(n^{4/3} log^{1/3} n + n^{2/3}k^{2/3} log 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} le k le n^2/log^6 n$▫. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs.20092015-07-10 15:08:20Delo ni kategorizirano51785sl