Disk embeddings of planar graphs

DOI10.1007/S00453-003-1055-0MaRDI QIDQ1879252zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen, Xin He

Publication date 22 September 2004

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-003-1055-0

zbMATH Keywords

graph algorithmplanar embeddingplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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.

Recommendations

• A linear algorithm for embedding planar graphs using PQ-trees
• Embedding planar graphs at fixed vertex locations
• scientific article; zbMATH DE number 475595
• scientific article; zbMATH DE number 1305401
• scientific article; zbMATH DE number 508832

Cited in

(7)

• Disk/band surfaces of spatial graphs
• On selecting leaves with disjoint neighborhoods in embedded trees
• Obedient plane drawings for disk intersection graphs
• scientific article; zbMATH DE number 1696628 (Why is no real title available?)
• A new characterization of disk graphs and its application.
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Linear-time algorithms for problems on planar graphs with fixed disk dimension

This page was built for publication: Disk embeddings of planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1879252)