A Linear-Time Algorithm for Five-Partitioning Five-Connected Internally Triangulated Plane Graphs

摘要

given a graph G=(V,E), five distinct vertices u1, u2, u3, u4, u5 ∈V and five natural numbers n1, n2, n3, n4, n5 such the formula (ill.) ni =|v|, we wish to find a partition V1,v2,v3,v4,ve of the vertex set v such that ui　∈ vi, |vi| =ni And Vi induces a connected subgraph of G for each I, 1 ≤i≤5.