Segment representation of a subclass of co-planar graphs
Segment representation of a subclass of co-planar graphs
复制标题
共面图子类的线段表示
DOI：
10.1016/j.disc.2012.01.024
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Tomás Vyskocil
中科院分区：
文献类型：
--
作者：
Mathew C. Francis;Jan Kratochvíl;Tomás Vyskocil
如果图的顶点可以映射到平面中的线段，并且当且仅当它们对应的线段相交时两个顶点相邻，则该图是线段图。 Kratochvíl 和 Kuběna 提出了平面图的补图（称为共平面图）是否是线段图的问题。我们在这里证明所有部分 2 树的补集都是线段图。
A graph is a segment graph if its vertices can be mapped to line segments in the plane such that two vertices are adjacent if and only if their corresponding line segments intersect. Kratochvíl and Kuběna asked the question of whether the complements of planar graphs, called co-planar graphs, are segment graphs. We show here that the complements of all partial 2-trees are segment graphs.