Intersection graphs of L-shapes and segments in the plane
Intersection graphs of L-shapes and segments in the plane
复制标题
L 形和平面内线段的交图
DOI：
10.1016/j.dam.2016.01.028
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
Felsner S
中科院分区：
文献类型：
--
作者：
Felsner S
L形是具有共同终点的水平段和垂直段的结合。它们有四个旋转：、和。K折弯路径是平面上的一条简单路径，其方向从水平到垂直变化k次。如果一个图允许一个交表示，其中每个顶点都由一个或、一条k弯路或一段线表示，那么这个图分别称为{}图、{，}图、Bk-VPG图或SEG图。受Middendorf和Pfeiffer(1992)的一个定理--每个{，}-图都是SEG-图的启发，我们研究了SEG-图类的几个已知的子类，证明了它们是{}-图，或对某个小常数k是Bk-VPG-图，我们证明了所有的平面3-树，平面图的所有线图，以及平面图的所有完全剖分都是{}-图。进一步证明了平面图的补是B17-VPG-图，完全剖分的补是B2-VPG-图。这里，完全细分是指每条边至少细分一次的图。
An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations:,, and. A k-bend path is a simple path in the plane, whose direction changes k times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an, an or, a k-bend path, or a segment, then this graph is called an {}-graph,{,}-graph, B k-VPG-graph or SEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer (1992), stating that every {,}-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are {}-graphs, or B k-VPG-graphs for some small constant k. We show that all planar 3-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are {}-graphs. Furthermore we show that complements of planar graphs are B 17-VPG-graphs and complements of full subdivisions are B 2-VPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once.
登录
查看更多内容
DOI：
10.1137/1.9781611973105.120
发表时间：
2012
期刊：
ArXiv
影响因子：
--
作者：
S. Kobourov;T. Ueckerdt;Kevin Verbeek
通讯作者：
Kevin Verbeek
影响因子：
1.1
作者：
H. D. Fraysseix;P. D. Mendez
通讯作者：
P. D. Mendez
DOI：
10.1016/j.disc.2012.01.024
发表时间：
2010
期刊：
Discret. Math.
影响因子：
--
作者：
Mathew C. Francis;Jan Kratochvíl;Tomás Vyskocil
通讯作者：
Tomás Vyskocil
DOI：
10.1016/s0012-365x(97)81834-1
发表时间：
1998
期刊：
Discret. Math.
影响因子：
--
作者：
Jan Kratochvíl;A. Kuběna
通讯作者：
A. Kuběna
平面图具有 1 串表示形式
影响因子：
0.8
作者：
Jérémie Chalopin;D. Gonçalves;P. Ochem
通讯作者：
P. Ochem