论文标题
棍子图：示例和反例
Stick graphs: examples and counter-examples
论文作者
论文摘要
网格相交图是平面中垂直和水平段的相交图。当垂直和水平段的底部和左端分别属于带负斜率的线时，该图称为棒图。棒图上很少有结果：仅确定了小类的棍子图；识别棍子图是一个开放的问题。即使构建非棍子图的图形示例也很棘手。 在本文中，我们首先证明了圆形图和圆形弧形图的补充是棍子图。然后，我们提出了两个证书，允许确定图形不是棒图，并使用它们来构建新的不粘图示例。事实证明，这些不粘图的例子以及所有文献的示例都有很长的孔。因此，我们还研究了围绕棍子图的类的层次结构中的和弦网格相交图的位置。
Grid intersection graphs are the intersection graphs of vertical and horizontal segments in the plane. When the bottom and respectively left endpoints of the vertical and horizontals segments belong to a line with negative slope, the graph is called a Stick graph. Very few results exist on Stick graphs: only small classes of Stick graphs have been identified; recognizing Stick graphs is an open problem; and even building examples of graphs that are not Stick graphs is quite tricky. In this paper, we first prove that the complements of circle graphs and of circular arc graphs are Stick graphs. Then, we propose two certificates allowing to decide that a graph is not a Stick graph, and use them to build new examples of non-Stick graphs. It turns out that these examples of non-Stick graphs, as well as all those from literature, have long holes. We thus also investigate the place of chordal grid intersection graphs in the hierarchy of classes built around Stick graphs.
