Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs

• We propose a distributed algorithm for the maximal 2-packing set in a geometric outerplanar graph.
• The execution time of this algorithm is O(n)O(n) steps.
• The algorithm has three phases: leader election, graph exploration, and vertex coloring.
• The vertex coloring phase resembles an ear decomposition of the input graph.
• When the input graph is a ring, the algorithm computes the maximum 2-packing set.

In this paper, we present a deterministic distributed algorithm that computes the maximal 2-packing set in a geometric outerplanar graph. In a geometric outerplanar graph, all the vertices have location coordinates in the plane and lie on the boundary of the graph. Our algorithm consists of three phases. First, it elects a vertex as the leader. Second, it explores the graph to determine relevant information about the structure of the input graph. Third, with this information, it computes a maximal 2-packing set. When the input graph is a ring, the algorithm computes a maximum 2-packing set. The execution time of this algorithm is O(n)O(n) steps and it uses O(nlogn)O(nlogn) messages. This algorithm does not require knowledge of the size of the input graph. To the best of our knowledge, this is the first deterministic distributed algorithm that solves such a problem for a geometric outerplanar graph in a linear number of steps.