TITLE: Small k-Dominating Sets in Planar Graphs with Applications AUTHORS: Cyril Gavoille, David Peleg, André Raspaud and Eric Sopena ABSTRACT: A subset of nodes S in a graph G is called k-dominating if, for every node u of the graph, the distance from u to S is at most k. We consider the parameter \gammak(G) defined as the cardinality of the smallest k-dominating set of G. For planar graphs, we show that for every e>0 and for every k>=(5/7+e)D, \gammak(G) = O(1/e). For several subclasses of planar graphs of diameter D, we show that \gammak(G) is bounded by a constant for k>=D/2. We conjecture that the same result holds for every planar graph. This problem is motivated by the design of routing schemes with compact data structures.