Disk embeddings of planar graphs (Q1879252)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Disk embeddings of planar graphs |
scientific article |
Statements
Disk embeddings of planar graphs (English)
0 references
22 September 2004
0 references
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.
0 references
planar embedding
0 references
graph algorithm
0 references
planar graph
0 references