论文标题
朝着可拉伸对齐图的表征
Towards a characterization of stretchable aligned graphs
论文作者
论文摘要
我们考虑在平面直线图中拉伸伪线的问题，同时保留图纸的直率和组合嵌入。我们回答了Mchedlidze等人的开放问题。通过表明并非所有具有两个伪线的实例都是可拉伸的。从积极的一面来看，对于$ k \ geq 2 $ pseudolines，单个点相交，我们证明，如果禁止某些边缘 - 释放相交模式，则所有实例都是可拉伸的。对于无相交的伪线布置，我们表明每个对齐的图都有一个对齐图。这大大减少了可拉伸和不易伸缩实例之间的差距。
We consider the problem of stretching pseudolines in a planar straight-line drawing to straight lines while preserving the straightness and the combinatorial embedding of the drawing. We answer open questions by Mchedlidze et al. by showing that not all instances with two pseudolines are stretchable. On the positive side, for $k\geq 2$ pseudolines intersecting in a single point, we prove that in case that some edge-pseudoline intersection-patterns are forbidden, all instances are stretchable. For intersection-free pseudoline arrangements we show that every aligned graph has an aligned drawing. This considerably reduces the gap between stretchable and non-stretchable instances.
