An algorithm for testing the planarity of a hierarchical graph

Suppose a graph G=(V,E) is given and a partition of V into K subsets V1,V2,...,VK, where ViℝVj=Θ for iℝj, and V1ℝV2ℝëëëℝVK=V. This paper presents an O(ℝVℝ) time algorithm for testing whether G has a planar embedding that satisfies the following two conditions. Condition 1:The vertices in Vi are placed on the ith horizontal line from the top for i=1,2,...,K. Condition 2:No edge crosses any horizontal line at two or more points. [In Japanese.]