On October 24, 2023, Robert Hickingbotham from Monash University gave a talk at the Discrete Math Seminar on the existence of a partition of a planar graph into connected induced subgraphs of bounded size so that all long paths intersect some part more than once and its application to k-planar graphs and powers of planar graphs. The title of his talk was “Powers of planar graphs, product structure, and blocking partitions“.
Graph product structure theory describes complex graphs in terms of products of simpler graphs. In this talk, I will introduce this subject and talk about some of my recent results in this area. The focus of my talk will be on a new tool in graph product structure theory called `blocking partitions.’ I’ll show how this tool can be used to prove stronger product structure theorems for powers of planar graphs as well as $k$-planar graphs, resolving open problems of Dujmović, Morin and Wood, and Ossona de Mendez.
On February 15, 2023, Robert Hickingbotham from Monash University gave an online talk at the Virtual Discrete Math Colloquium on the relation between the tree-width and the Hadwiger number of circle graphs. The title of his talk was “Treewidth, Circle Graphs and Circular Drawings“.
A circle graph is an intersection graph of a set of chords of a circle. In this talk, I will 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. I will also discuss applications of our results to the treewidth of graphs $G$ that have a circular drawing whose crossing graph is well-behaved in some way. In this setting, our results 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, I’ll present a construction of graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are $2$-degenerate. This is joint work with Freddie Illingworth, Bojan Mohar, and David R. Wood
