On Graphs Supported by Line Sets
On Graphs Supported by Line Sets
复制标题
关于线集支持的图
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Wismath
中科院分区：
文献类型：
--
作者：
V. Dujmović;W. Evans;S. Kobourov;G. Liotta;Christophe Weibel;S. Wismath
对于一个由n条标号为1到n的线组成的集合S，我们说S支撑一个n-顶点平面图G，如果对于它的每个标号从1到n的顶点，G有一个直线无交图，每个顶点都画成它的关联线上的一个点。从以前的工作[4]中可以知道，没有n条平行线的集合支持所有n-顶点平面图。我们表明，相交线，即使他们相交于一个共同点，是更“强大”的一组平行线。特别是，我们证明了每一个这样的一组线支持outerpaths，龙虾，鱿鱼，没有一个是支持任何一组平行线。在消极的一面，我们证明了没有一组n线相交于一个公共点支持所有的n-顶点平面图。最后，我们证明了存在一组n线在一般位置，不支持所有的n-顶点平面图。
For a set S of n lines labeled from 1 to n, we say that S supports an n-vertex planar graph G if for every labeling from 1 to n of its vertices, G has a straight-line crossing-free drawing with each vertex drawn as a point on its associated line. It is known from previous work [4] that no set of n parallel lines supports all n-vertex planar graphs. We show that intersecting lines, even if they intersect at a common point, are more "powerful" than a set of parallel lines. In particular, we prove that every such set of lines supports outerpaths, lobsters, and squids, none of which are supported by any set of parallel lines. On the negative side, we prove that no set of n lines that intersect in a common point supports all n-vertex planar graphs. Finally, we show that there exists a set of n lines in general position that does not support all n-vertex planar graphs.