Disk embeddings of planar graphs

Given a planar graph G=(V,E) and a rooted forest script F sign = (V _{script F sign}, A_{script F sign}) with leaf set V, we wish to decide whether G has a plane embedding script G sign satisfying the following condition: There are |V script F sign|-|V| pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of script F sign such that for every nonleaf vertex f of script F sign, the interior of the curve Jf corresponding to f contains all the leaf descendants of f in script F sign but contains no other leaves of script F sign. This problem arises from theoretical studies in geographic database systems. It is unknown whether this problem can be solved in polynomial time. This paper presents an almost linear-time algorithm for a nontrivial special case where the set of leaf descendants of each nonleaf vertex f in script F sign induces a connected subgraph of G.