Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases

摘要

This paper describes linear algorithms for partitioning a planar graph into k edge-disjoint connected subgraphs, each of which has a specified number of vertices and edges. If e(≤ k) subgraphs contain the specified elements(called bases), we call this problem the k-partition problem with e-base (denoted by k-PART-B(e)). In this paper, we obtain the following results: (1)for any k ≥ 2, k-PART-B(1) can be solved in O(|E|) time for every 4-edge-connected planar graph G = (V,E), (2)3-PART-B(1) can be solved in O(|E|) time for every 2-edge-connected planar graph G = (V,E) and (3)5-PART-B(1) can be solved in O(|E|) time for every 3-edge-connected planar graph G = (V, E).