We study a fundamental question from graph drawing: given a pair $(G,C)$ of a graph $G$ and a cycle $C$ in $G$ together with a simple polygon $P$, is there a straight-line drawing of $G$ inside $P$ which maps $C$ to $P$? We say that such a drawing of $(G,C)$ respects $P$. We fully characterize those instances $(G,C)$ which are polygon-universal, that is, they have a drawing that respects $P$ for any simple (not necessarily convex) polygon $P$. Specifically, we identify two necessary conditions for an instance to be polygon-universal. Both conditions are based purely on graph and cycle distances and are easy to check. We show that these two conditions are also sufficient. Furthermore, if an instance $(G,C)$ is planar, that is, if there exists a planar drawing of $G$ with $C$ on the outer face, we show that the same conditions guarantee for every simple polygon $P$ the existence of a planar drawing of $(G,C)$ that respects $P$. If $(G,C)$ is polygon-universal, then our proofs directly imply a linear-time algorithm to construct a drawing that respects a given polygon $P$.
翻译:我们从图表绘制中研究了一个根本性问题:如果给一对一对(G,C)美元(G,G)美元,一对美元(G,C)美元周期(G)美元(G)美元,加上一个简单的多边方元美元,那么在美元内部是否有直线绘制的G美元(G,C)美元(P美元)直线绘制的美元(G,C)美元(P美元)?我们说,这种(G,C)美元(G,C)美元(G,C)美元(G,C)美元(G,C)美元(P)美元(P美元)的图案,如果有美元(P)美元(P)的平面图案(P),那么,我们为每个简单多边方美元(P)的票案(P)确定两个必要条件。两种条件都纯粹以图形和周期距离为基础,而且很容易检查。我们说,这两种条件都足够了。此外,如果(G,)美元(C)美元(G)美元(C)的平面图案(US美元)的正数(G)代表直数(G)的正数(G)的正数(G)。