论文标题
树宽，圆形图和圆形图纸
Treewidth, Circle Graphs and Circular Drawings
论文作者
论文摘要
圆形图是一组圆的和弦的相交图。我们描述了具有较大树宽的圆形图的不可避免的诱导子图。这包括与“常规嫌疑人”相去甚远的例子。我们的结果表明，在圆形图的类别上，树宽和Hadwiger编号是线性捆绑的，并且仅当该类别的等级范围有界限时，不可避免的有点限制的具有较大树宽的顶点限制的类别是较大的treewidth。使用相同的工具，我们还研究了具有圆形图的图形$ g $的树宽，其交叉图在某种程度上是良好的。在这种情况下，我们表明，如果交叉图为$ k_t $ -minor-free，则$ g $最多具有$ 12T-23 $，并且没有$ k_ {2,4t} $ - 拓扑小调。另一方面，我们证明有一些任意大的hadwiger编号的图形，其圆形图形的交叉图为$ 2 $ - 定位。
A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects'. Our results imply that treewidth and Hadwiger number are linearly tied on the class of circle graphs, and that the unavoidable induced subgraphs of a vertex-minor-closed class with large treewidth are the usual suspects if and only if the class has bounded rank-width. Using the same tools, we also study the treewidth of graphs $G$ that have a circular drawing whose crossing graph is well-behaved in some way. In this setting, we show that if the crossing graph is $K_t$-minor-free, then $G$ has treewidth at most $12t-23$ and has no $K_{2,4t}$-topological minor. On the other hand, we show that there are graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are $2$-degenerate.
