We consider the construction of sparse covers for planar graphs and other graphs that exclude a fixed minor. We present an algorithm that gives a cover for the γ-neighborhood of each node. For planar graphs, the cover has radius less than 16γ and degree no more than 18. For every n node graph that excludes a minor of a fixed size, we present an algorithm that yields a cover with radius no more than 4γ and degree O(logn).
This is a significant improvement over previous results for planar graphs and for graphs excluding a fixed minor; in order to obtain clusters with radius O(γ), it was required to have the degree polynomial in n. Our algorithms are based on a recursive application of a basic routine called shortest-path clustering, which seems to be a novel approach to the construction of sparse covers.
Since sparse covers have many applications in distributed computing, including compact routing, distributed directories, synchronizers, and Universal TSP, our improved cover construction results in improved algorithms for all these problems, for the class of graphs that exclude a fixed minor.
Available at: http://works.bepress.com/srikanta-tirthapura/41/
This is a manuscript of an article published as Busch, Costas, Ryan LaFortune, and Srikanta Tirthapura. "Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor." Algorithmica 69, no. 3 (2014): 658-684. The final publication is available at Springer via DOI: 10.1007/s00453-013-9757-4. Posted with permission.