A Linear Algorithm for Resource Four-partitioning Four-connected Planar Graphs

Abstract

Given a connected graph G = (V, E), a set V_r ⊆ V of r special vertices, four distinct base vertices u₁, u₂, u₃, u₄ ∊ V and four natural numbers r₁, r₂, r₃, r₄ such that Σ⁴_j=1 r_j = r, we wish to find a partition V₁, V₂, V₃, V₄ of V such that V_i contains u_i and r_i vertices from V_r, and V_i induces a connected subgraph of G for each i, 1 ≤ i ≤ 4. We call a vertex in V_r a resource vertex and the problem above of partitioning vertices of G as the resource 4-partitioning problem. In this paper, we give a linear algorithm for finding a resource 4-partition of a 4-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 an st-numbering of G.

Keywords:

• Algorithm
• 4-canonical decomposition
• Four-partition
• Four-connected graph
• Planar graph
• st-numbering
• Resource bipartition
• Resource four-partition

2010 Mathematics Subject Classification:

• 05C85
• 05C10