Resource partitioning on planar graphs

Abstract

Numerous applications of resource partitioning have been found in electrical power distribution systems, telecommunication networks, computer networks, fault tolerant systems, grid computing etc. The resource partitioning problem is concerned with finding a k-resource partitioning of a given graph. In this problem, given a connected graph G = (V, E), k distinct base vertices UI, U2, ... ,Uk E V, a set 11;. <;;; V of T special vertices called resource vertices and k natural numbers TI,T2, ... , Tk such that L::~ITi = T, we wish to find a partition VI, V2, ... , Vk of the vertex set V such that V; contains Ui along with T, resource vertices, V; induces a connected subgraph of G for each 'i, 1 ::; i ::;k. In this thesis we present linear-time algorithms for computing a resource tripartition of a 3-connected planar graph and a resource four-partition of a 4-connected planar graph. To solve the resource tripartitioning problem, we have developed a linear-time algorithm for constructing a. nonseparating em decomposition through two vertices a, b and avoiding a third vertex c of a 3-connected graph G for 3J'Y three vertices a, b, c. We also give bounds on the number of ears and the length of an ear for the nonscparating ear decomposition produced by our algorithm.