Disk embeddings of planar graphs (Q1879252): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00453-003-1055-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2051231876 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 23:09, 19 March 2024
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