A Linear Algorithm for Resource Tripartitioning Triconnected Planar Graphs

Abstract

Given a connected graph G = (V,E), a set Vr ⊆ V of r special vertices, three distinct base vertices u1, u2, u3 ∈ V and three natural numbers r1, r2, r3 such that r1 + r2 + r3 = r, we wish to find a partition V1, V2, V3 of V such that Vi contains ui and ri vertices from Vr, and Vi induces a connected subgraph of G for each i, 1 ≤ i ≤ 3. We call a vertex in Vr a resource vertex and the problem above of partitioning vertices of G as the resource 3-partitioning problem. In this paper, we give a linear-time algorithm for finding a resource tripartition of a 3-connected planar graph G. Our algortihm is based on a nonseparating ear decomposition of G and st-numbering of G. We also present a linear algorithm to
find a nonseparating ear decomposition of a 3-connected planar graph. This algorithm has bounds on ear-length and number of ears.