Straight line embeddings of rooted star forests in the plane (Q1975369)

Fáry's theorem asserts that any finite planar graph has a straight-line embedding in the plane (i.e., one in which the edges are represented by straight-line segments). The present work investigates the possibility of finding a straight-line embedding in which the vertices correspond to arbitrarily chosen points in the plane---it is known, for example, that any outerplanar graph with \(n\) vertices has a straight-line embedding in which the vertices correspond to any given set of \(n\) points in the plane in general position. The authors study this question for rooted star forests, that is, for forests whose components are all stars, and for which one vertex (called the ``root'') is distinguished from each component. They show: given any rooted star forest \(F\) with \(n\) vertices and \(c\) components, any set \(S\) of \(n\) points in the plane in general position and any subset \(R\) of \(c\) of these points, \(F\) has a straight-line embedding in the plane in which the vertices correspond to the points in \(S\) and the roots to the points in \(R\). A simple example shows that the hypothesis that each component be a star cannot be dropped, in general.