Many distances in planar graphs

Abstract

We 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.

Keywords

matematika;teorija grafov;ravninski graf;razdalja;mathematics;graph theory;planar graph;distance;

Data

Language:	English
Year of publishing:	2009
Typology:	0 - Not set
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	15142233
ISSN:	1318-4865
Views:	33
Downloads:	7
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary keywords:	matematika;teorija grafov;ravninski graf;razdalja;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1-18
Volume:	ǂVol. ǂ47
Issue:	ǂšt. ǂ1089
Chronology:	2009
ID:	1474262