























A subset $S$ of vertices in a planar graph $G$ is a free set if, for every set $P$ of $|S|$ points in the plane, there exists a straight-line crossing-free drawing of $G$ in which vertices of $S$ are mapped to distinct points in $P$. In this survey, we review - several equivalent definitions of free sets, - results on the existence of large free sets in planar graphs and subclasses of planar graphs, - and applications of free sets in graph drawing. The survey concludes with a list of open problems in this still very active research area.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。