文章基本信息

标题：Local Routing in Sparse and Lightweight Geometric Graphs
本地全文：下载
作者：Vikrant Ashvinkumar ; Joachim Gudmundsson ; Christos Levcopoulos 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：149
页码：1-13
DOI：10.4230/LIPIcs.ISAAC.2019.30
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Bose and Morin, 2004] showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega(n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.
关键词：Computational geometry; Spanners; Routing