A linear algorithm for resource four-partitioning four-connected planar graphs
Tanveer Awal, Md. Saidur Rahman · 2010
Given a connected graph G = (V,E), a set Vr⊆ V of r special vertices, four distinct base vertices u1, u2, u3, u4∈ V and four natural numbers r1, r2, r3, r4such that Σj=14rj= r, we wish to find a partition V1, V2, V3, V4of V such that Vicontains uiand rivertices from Vr, and Viinduces a connected subgraph of G for each i, 1 ≤ i ≤ 4. We call a vertex in Vra resource vertex and the problem above of partitioning vertices of G as the resource four-partitioning problem. In this paper, we give a linear algorithm for finding a resource four-partition of a four-connected planar graph G with base vertices located on the same face of a planar embedding. Our algorithm is based on a 4-canonical decomposition and st-numbering of G.