Treewidth, Circle Graphs, and Circular Drawings
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 …