An algorithm for testing the planarity of a hierarchical graph
Toshinobu Kashiwabara, Sumio Masuda · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1992
Abstract Suppose that a graph G = (V, E) and a partition V1, V2, …, Vk (where Vi ∩ Vj = ϕ(i≠j), V1 ∪ V2 ∪ … ∪ Vk = V) of V into K subsets are given. If a vertex v belongs to a set Vi, the level of v is said to be i. This paper proposes an algorithm which tests whether or not there is a planar embedding of G satisfying the following two conditions. Condition 1. The vertices are arranged from top to bottom in the increasing order of their level (the vertices of the same level are placed on one horizontal line). Condition 2. An edge crosses a horizontal line at most at one point. This algorithm uses a data structure called the PQ‐tree and it can be executed in O(|V|) time.