Disk embeddings of planar graphs (Q1879252): Difference between revisions

Let \(G=(V,E)\) be a planar graph. Given a rooted forest \(F=(V_F,A_F)\) with leaf set \(V\), one has to decide whether there is a plane embedding of \(G\) with the property that there are \(| V_F| -| V| \) pairwise noncrossing Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of \(F\) such that for every nonleaf vertex \(f\) of \(F\) the interior of the curve corresponding to \(f\) contains all the leaf descendants of \(f\) in \(F\) but contains no other leaves of \(F\). The authors give an almost linear-time algorithm for a special case of this problem.