We develop a linear time algorithm for the following problem: Given a graph G and a hieerarchical clustering of the vertices such that all clusters induce connected subgraphs, determine whether G may be embedded into the plane such that no cluster has a hole. This is an improvement to the O(n sup 2)-algorithm of Q.W. Feng et al. [6] and the algorithm of Lengauer [12] that operates in linear time on a replacement system. the size of the input of Lengauer's algorithm is not necessarily linear with respect to the number of vertices.
展开▼
