论文标题
绘制两个posets
Drawing Two Posets
论文作者
论文摘要
我们研究了绘制同一接地组的两个poset的问题，以便从左到右绘制一个poset，另一个是从底部绘制的。此问题的输入是有向图$ g =（v，e）$和两个套装$ x，y $，带有$ x \ cup y = e $，每个$可以解释为$ v $的部分订单。任务是找到$ g $的平面图，以便将$ x $中的每个定向边缘绘制为$ x $ - 单酮边缘，并且$ y $中的每个定向边缘都被绘制为$ y $ $ $ - 单酮边缘。这样的图纸称为$ xy $ - 平面图。 测试图表是否承认$ xy $ - 平面图是NP完整的。我们认为，$ g $的平面嵌入是固定的，并且边缘以$ y $引起的$ g $的子图是$ g $的连接子图，其向上嵌入的固定是固定的。在这种情况下，我们提出了一种线性时间算法，该算法确定$ g $是否允许$ xy $ - 平面图，如果是的，则可以产生$ xy $ - 平面的多线线绘图，最多可以每3弯。
We investigate the problem of drawing two posets of the same ground set so that one is drawn from left to right and the other one is drawn from the bottom up. The input to this problem is a directed graph $G = (V, E)$ and two sets $X, Y$ with $X \cup Y = E$, each of which can be interpreted as a partial order of $V$. The task is to find a planar drawing of $G$ such that each directed edge in $X$ is drawn as an $x$-monotone edge, and each directed edge in $Y$ is drawn as a $y$-monotone edge. Such a drawing is called an $xy$-planar drawing. Testing whether a graph admits an $xy$-planar drawing is NP-complete in general. We consider the case that the planar embedding of $G$ is fixed and the subgraph of $G$ induced by the edges in $Y$ is a connected spanning subgraph of $G$ whose upward embedding is fixed. For this case we present a linear-time algorithm that determines whether $G$ admits an $xy$-planar drawing and, if so, produces an $xy$-planar polyline drawing with at most three bends per edge.
