Spanners for Geometric Intersection Graphs

详细信息    查看全文

• 作者：Martin Fürer ; Shiva Prasad Kasiviswanathan
• 刊名：Lecture Notes in Computer Science
• 出版年：2007
• 出版时间：2007
• 年：2007
• 卷：4619
• 期：1
• 页码：312-324
• 全文大小：498 KB
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

A disk graph is an intersection graph of a set of disks with arbitrary radii in the plane. In this paper, we consider the problem of efficient construction of sparse spanners of disk (ball) graphs with support for fast distance queries. These problems are motivated by issues arising from topology control and routing in wireless networks. We present the first algorithm for constructing spanners of ball graphs. For a ball graph in l = 1-1/(?k/2 ?+2)\ell=1-1/(\lfloor k/2 \rfloor+2) , δ is any positive constant, and S is the ratio between the largest and smallest radius. For the special case where all the balls have the same radius, we show that the spanner construction has complexity almost equivalent to the construction of a Euclidean minimum spanning tree. Previously known constructions of spanners of unit ball graphs have time complexity much closer to n 2. Additionally, these spanners have a small vertex separator (hereditary), which is then exploited for fast answering of distance queries. The results on geometric graph separators might be of independent interest.