Hickingbotham, Robert; Illingworth, Freddie; Mohar, Bojan; Wood, David R; (2024) Treewidth, Circle Graphs, and Circular Drawings. SIAM Journal on Discrete Mathematics , 38 (1) pp. 965-987. 10.1137/22m1542854.

Preview

Text circle_graphs_SIDMA.pdf - Published Version Download (618kB) | Preview

Abstract

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 Kt-minor-free, then G has treewidth at most 12t - 23 and has no K2,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.

Download activity - last month

Export as CSVJSONXML

Download activity - last 12 months

Export as CSVJSONXML

Downloads by country - last 12 months

Export as XMLJSONCSV

Archive Staff Only

View Item