Treewidth, Circle Graphs, and Circular Drawings

. 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ₜ\) -minor-free, then \ (G\) has treewidth at most \ (12t-23\) and has no \ (K₂, ₄ₓ\) -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. Keywordscircle graphstreewidthcircular drawingsMSC codes05C8305C1005C62