论文标题
向上点设置路径和树木的嵌入
Upward Point Set Embeddings of Paths and Trees
论文作者
论文摘要
我们在给定的点集中研究了定向树的向上平面直线嵌入（UPSE）。给定的点集$ s $至少具有树上的顶点数。对于特殊情况，树是路径$ p $我们显示的：（a）如果$ s $是单侧凸，则UPSES的数量等于$ p $中的最大单调路径的数量。 （b）如果$ s $的一般位置，$ p $由三个最大单调路径组成，中间路径比其他两个路径更长，那么它总是在$ s $上承认UPSE。我们表明，是否存在$ n $顶点在固定点集合$ n $点上有$ n $顶点的upse的决策问题是np-complete，这是通过放松以前已知的结果的要求，该结果依赖于图中存在周期的情况，而是固定单个顶点的位置。最后，通过允许多点积分，我们保证每个指向$ n $顶点的毛毛虫，并且$ k $开关的骨架都可以在每组$ n 2^{k-2} $点上承认upse。
We study upward planar straight-line embeddings (UPSE) of directed trees on given point sets. The given point set $S$ has size at least the number of vertices in the tree. For the special case where the tree is a path $P$ we show that: (a) If $S$ is one-sided convex, the number of UPSEs equals the number of maximal monotone paths in $P$. (b) If $S$ is in general position and $P$ is composed by three maximal monotone paths, where the middle path is longer than the other two, then it always admits an UPSE on $S$. We show that the decision problem of whether there exists an UPSE of a directed tree with $n$ vertices on a fixed point set $S$ of $n$ points is NP-complete, by relaxing the requirements of the previously known result which relied on the presence of cycles in the graph, but instead fixing position of a single vertex. Finally, by allowing extra points, we guarantee that each directed caterpillar on $n$ vertices and with $k$ switches in its backbone admits an UPSE on every set of $n 2^{k-2}$ points.
