Treewidth, Circle Graphs and Circular Drawings

التفاصيل البيبلوغرافية
العنوان: Treewidth, Circle Graphs and Circular Drawings
المؤلفون: Hickingbotham, Robert, Illingworth, Freddie, Mohar, Bojan, Wood, David R.
سنة النشر: 2022
المجموعة: Mathematics
مصطلحات موضوعية: Mathematics - Combinatorics, 05C83, 05C10, 05C62
الوصف: 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.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2212.11436
رقم الأكسشن: edsarx.2212.11436
قاعدة البيانات: arXiv