An Approximation Algorithm for Generalized Connectivity Problem on Planar Graphs

Let [Formula: see text] be a graph with nonnegative edge weight function [Formula: see text] and [Formula: see text] be the set of demands, where [Formula: see text] and [Formula: see text] are distinct vertex subsets for each demand [Formula: see text]. The objective of generalized connectivity is to find a subgraph [Formula: see text] with minimum weight such that for each demand [Formula: see text], there exists a path in [Formula: see text] connecting [Formula: see text] and [Formula: see text]. In this paper, we consider the planar generalized connectivity problem, i.e., [Formula: see text] is a planar graph, and design a [Formula: see text]-approximation algorithm via the junction scheme, along with bucketing-and-scaling technique.