Treewidth, Circle Graphs and Circular Drawings

A circle graph is the intersection graph of a set of chords of a circle. Circle graphs form a widely studied graph class [35, 50, 22, 20, 18, 31, 47] and there have been several recent breakthroughs concerning them. In the study of graph colourings, Davies and McCarty [20] showed that circle graphs are quadratically $\chi$-bounded improving upon a previous longstanding exponential upper bound. Davies [18] further improved this bound to $\chi(G)\in\mathcal{O}(\omega(G)\log\omega(G))$, which is best possible. Circle graphs are also fundamental to the study of vertex-minors and are conjectured to lie at the heart of a global structure theorem for vertex-minor-closed graph classes (see [54]). To this end, Geelen, Kwon, McCarty, and Wollan [35] recently proved an analogous result to the excluded grid minor theorem for vertex-minors using circle graphs. In particular, they showed that a vertex-minor-closed graph class has bounded rankwidth if and only if it excludes a circle graph as a vertex-minor. For further motivation and background on circle graphs, see [19, 54].

Our first contribution essentially determines when a circle graph has large treewidth.

Observe that in Theorem 1 the subgraph $H$ has a $K_{\_}t$-minor obtained by contracting each of the cycles $C_{\_}i$ to a single vertex, implying that $H$ has treewidth at least $t-1$. Moreover, since circle graphs are closed under taking induced subgraphs, $H$ is also a circle graph. We now highlight several consequences of Theorem 1.

First, Theorem 1 describes the unavoidable induced subgraphs of circle graphs with large treewidth. Recently, there has been significant interest in understanding the induced subgraphs of graphs with large treewidth [51, 8, 6, 7, 3, 4, 5, 62, 72, 13, 2]. To date, most of the results in this area have focused on graph classes where the unavoidable induced subgraphs are the following graphs, the usual suspects: a complete graph $K_{\_}t$, a complete bipartite graph $K_{\_}{t,t}$, a subdivision of the ($t\times t$)-wall, or the line graph of a subdivision of the ($t\times t$)-wall (see [72] for definitions). Circle graphs do not contain subdivisions of large walls nor the line graphs of subdivisions of large walls and there are circle graphs of large treewidth that do not contain large complete graphs nor large complete bipartite graphs (see Theorem 21). To the best of our knowledge this is the first result to describe the unavoidable induced subgraphs of the large treewidth graphs in a natural hereditary class when they are not the usual suspects. Later we show that the unavoidable induced subgraphs of graphs with large treewidth in a vertex-minor-closed class $\mathcal{G}$ are the usual suspects if and only if $\mathcal{G}$ has bounded rankwidth (see Theorem 23).

Second, the subgraph $H$ in Theorem 1 is an explicit witness to the large treewidth of $G$ (with only a multiplicative loss). Circle graphs being $\chi$-bounded says that circle graphs with large chromatic number must contain a large clique witnessing this. Theorem 1 can therefore be considered to be a treewidth analogue to the $\chi$-boundedness of circle graphs. We also prove an analogous result for circle graphs with large pathwidth (see Theorem 22).

Third, since the subgraph $H$ has a $K_{\_}t$-minor, it follows that every circle graph contains a complete minor whose order is at least one twelfth of its treewidth. This is in stark contrast to the general setting where there are $K_{\_}5$-minor-free graphs with arbitrarily large treewidth (for example, grids). Theorem 1 also implies the following relationship between the treewidth, Hadwiger number and Hajós number of circle graphs (see Section 5)¹¹1For a graph class $\mathcal{G}$, two graph parameters $\alpha$ and $\beta$ are tied on $\mathcal{G}$ if there exists a function $f$ such that $\alpha(G)\leqslant f(\beta(G))\text{ and }\beta(G)\leqslant f(\alpha(G))$ for every graph $G\in\mathcal{G}$. Moreover, $\alpha$ and $\beta$ are quadratically/linearly tied on $\mathcal{G}$ if $f$ may be taken to be quadratic/linear..

The second thread of this paper aims to understand the relationship between circular drawings of graphs and their crossing graphs. A circular drawing (also called convex drawing) of a graph places the vertices on a circle with edges drawn as straight line segments. Circular drawings are a well-studied topic; see [48, 73, 34] for example. The crossing graph of a drawing $D$ of a graph $G$ has vertex-set $E(G)$ where two vertices are adjacent if the corresponding edges cross. Circle graphs are precisely the crossing graphs of circular drawings. If a graph has a circular drawing with a well-behaved crossing graph, must the graph itself also be well-behaved? Graphs that have a circular drawing with no crossings are exactly the outerplanar graphs, which have treewidth at most 2. Put another way, outerplanar graphs are those that have a circular drawing whose crossing graph is $K_{\_}2$-minor-free. Our next result extends this fact, relaxing ‘$K_{\_}2$-minor-free’ to ‘$K_{\_}t$-minor-free’.

Theorem 3 says that $G$ having large treewidth is sufficient to force a complicated crossing graph in every circular drawing of $G$. A topological $K_{\_}{2,4t}$-minor also suffices.

Outerplanar graphs are exactly those graphs that have treewidth at most 2 and exclude a topological $K_{\_}{2,3}$-minor. As such, Theorems 3 and 4 extends these structural properties of outerplanar graphs to graphs with circular drawings whose crossing graphs are $K_{\_}t$-minor-free. We also prove a product structure theorem for such graphs, showing that every graph that has a circular drawing whose crossing graph has no $K_{\_}t$-minor is isomorphic to a subgraph of $H\boxtimes K_{\_}{\mathcal{O}(t^{3})}$ where $\operatorname{tw}(H)\leqslant 2$ (see Corollary 11).

In the other direction, we consider sufficient conditions for a graph $G$ to have a circular drawing whose crossing graph has no $K_{\_}t$-minor. By Theorems 3 and 4, $G$ must have bounded treewidth and no $K_{\_}{2,4t}$-topological minor. While these conditions are necessary, we show that they are not sufficient, but that bounded treewidth with bounded maximum degree is; see Lemma 17 and Proposition 18 in Section 4.2 for details.

In addition, we show that the assumption in Theorem 3 that the crossing graph has bounded Hadwiger number cannot be weakened to bounded degeneracy. In particular, we construct graphs with arbitrarily large complete graph minors that have a circular drawing whose crossing graph is $2$-degenerate (Theorem 19). This result has applications to the study of general (non-circular) graph drawings, and in particular, leads to the solution of an open problem asked by Hickingbotham and Wood [41].

Our proofs of Theorems 1, 3 and 2 are all based on the same core lemmas proved in Section 3. The results about circle graphs are in Section 5, while the results about graph drawings are in Section 4.

We use standard graph-theoretic definitions and notation; see [23].

For a tree $T$, a $T$-decomposition of a graph $G$ is a collection $\mathcal{W}=(W_{\_}x\colon x\in V(T))$ of subsets of $V(G)$ indexed by the nodes of $T$ such that (i) for every edge $vw\in E(G)$, there exists a node $x\in V(T)$ with $v,w\in W_{\_}x$; and (ii) for every vertex $v\in V(G)$, the set $\{x\in V(T)\colon v\in W_{\_}x\}$ induces a (connected) subtree of $T$. Each set $W_{\_}x$ in $\mathcal{W}$ is called a bag. The width of $\mathcal{W}$ is $\max\{\lvert W_{\_}x\rvert\colon x\in V(T)\}-1$. A tree-decomposition is a $T$-decomposition for any tree $T$. The treewidth $\operatorname{tw}(G)$ of a graph $G$ is the minimum width of a tree-decomposition of $G$.

A path-decomposition of a graph $G$ is a $T$-decomposition where $T$ is a path. The pathwidth $\operatorname{pw}(G)$ of a graph $G$ is the minimum width of a path-decomposition of $G$.

A graph $H$ is a minor of a graph $G$ if $H$ is isomorphic to a graph obtained from a subgraph of $G$ by contracting edges. The Hadwiger number $h(G)$ of a graph $G$ is the maximum integer $t$ such that $K_{\_}t$ is a minor of $G$.

A graph $\tilde{G}$ is a subdivision of a graph $G$ if $\tilde{G}$ can be obtained from $G$ by replacing each edge ${vw}$ by a path $P_{\_}{vw}$ with endpoints $v$ and $w$ (internally disjoint from the rest of $\tilde{G}$). A graph $H$ is a topological minor of $G$ if a subgraph of $G$ is isomorphic to a subdivision of $H$. The Hajós number $h^{\prime}(G)$ of $G$ is the maximum integer $t$ such that $K_{\_}t$ is a topological minor of $G$. A graph $G$ is $H$-topological minor-free if $H$ is not a topological minor of $G$.

It is well-known that for every graph $G$,

A graph class is a collection of graphs closed under isomorphism. A graph parameter is a real-valued function $\alpha$ defined on all graphs such that $\alpha(G_{\_}1)=\alpha(G_{\_}2)$ whenever $G_{\_}1$ and $G_{\_}2$ are isomorphic.

A drawing of a graph $G$ is a function $\phi$ that maps each vertex $v\in V(G)$ to a point $\phi(v)\in\mathbb{R}^{2}$ and maps each edge $e=vw\in E(G)$ to a non-self-intersecting curve $\phi(e)$ in $\mathbb{R}^{2}$ with endpoints $\phi(v)$ and $\phi(w)$, such that:

• •

  $\phi(v)\neq\phi(w)$ for all distinct vertices $v$ and $w$;

• •

  $\phi(x)\not\in\phi(e)$ for each edge $e=vw$ and each vertex $x\in V(G)\setminus\{v,w\}$;

• •

  each pair of edges intersect at a finite number of points: $\phi(e)\cap\phi(f)$ is finite for all distinct edge $e,f$; and

• •

  no three edges internally intersect at a common point: for distinct edges $e,f,g$ the only possible element of $\phi(e)\cap\phi(f)\cap\phi(g)$ is $\phi(v)$ where $v$ is a vertex incident to all of $e,f,g$.

A crossing of distinct edges $e=uv$ and $f=xy$ is a point in $(\phi(e)\cap\phi(f))\setminus\{\phi(u),\phi(v),\phi(x),\phi(y)\}$; that is, an internal intersection point. A plane graph is a graph $G$ equipped with a drawing of $G$ with no crossings.

The crossing graph of a drawing $D$ of a graph $G$ is the graph $X_{\_}D$ with vertex set $E(G)$, where for each crossing between edges $e$ and $f$ in $D$, there is an edge of $X_{\_}D$ between the vertices corresponding to $e$ and $f$. Note that $X_{\_}D$ is actually a multigraph, where the multiplicity of $ef$ equals the number of times $e$ and $f$ cross in $D$. In most drawings that we consider, each pair of edges cross at most once, in which case $X_{\_}D$ has no parallel edges.

Numerous papers have studied graphs that have a drawing whose crossing graph is well-behaved in some way. Here we give some examples. The crossing number $\operatorname{cr}(G)$ of a graph $G$ is the minimum number of crossings in a drawing of $G$; see the surveys [68, 60, 74] or the monograph [67]. Obviously, $\operatorname{cr}(G)\leqslant k$ if and only if $G$ has a drawing $D$ with $\lvert E(X_{\_}D)\rvert\leqslant k$. Tutte [75] defined the thickness of a graph $G$ to be the minimum number of planar graphs whose union is $G$; see [43, 55] for surveys. Every planar graph can be drawn with its vertices at prespecified locations [38, 61]. It follows that a graph $G$ has thickness at most $k$ if and only if $G$ has a drawing $D$ such that $\chi(X_{\_}D)\leqslant k$. A graph is $k$-planar if $G$ has a drawing $D$ in which every edge is in at most $k$ crossings; that is, $X_{\_}D$ has maximum degree at most $k$; see [59, 36, 28, 27] for example. More generally, Eppstein and Gupta [33] defined a graph $G$ to be $k$-degenerate crossing if $G$ has a drawing $D$ in which $X_{\_}D$ is $k$-degenerate. Bae et al. [9] defined a graph $G$ to be $k$-gap-planar if $G$ has a drawing $D$ in which each crossing can be assigned to one of the two involved edges and each edge is assigned at most $k$ of its crossings. This is equivalent to saying that every subgraph of $X_{\_}D$ has average degree at most $2k$. It follows that every $k$-degenerate crossing graph is $k$-gap-planar, and every $k$-gap-planar graph is a $2k$-degenerate crossing graph [44].

A drawing is circular if the vertices are positioned on a circle and the edges are straight line segments. A theme of this paper is to study circular drawings $D$ in which $X_{\_}D$ is well-behaved in some way. Many papers have considered properties of $X_{\_}D$ in this setting. The convex crossing number of a graph $G$ is the minimum number of crossings in a circular drawing of $G$; see [68] for a detailed history of this topic. Obviously, $G$ has convex crossing number at most $k$ if and only if $G$ has a circular drawing $D$ with $\lvert E(X_{\_}D)\rvert\leqslant k$. The book thickness (also called page-number or stack-number) of a graph $G$ can be defined as the minimum, taken over all circular drawings $D$ of $G$, of $\chi(X_{\_}D)$. This parameter is widely studied; see [30, 26, 10, 45, 78, 79] for example.

Here we prove that for any drawing $D$ of a graph $G$, the radius of $M_{\_}D$ acts as an upper bound for both the treewidth of $G$ and the treewidth of $X_{\_}D$.

Wood and Telle [77, Prop. 8.5] proved that if a graph $G$ has a circular drawing $D$ such that whenever edges $e$ and $f$ cross, $e$ or $f$ crosses at most $d$ edges, then $G$ has treewidth at most $3d+11$. This assumption implies $\operatorname{rad}(M_{\_}D)\leqslant\lfloor d/2\rfloor+1$ and so the first inequality of Theorem 5 generalises this result.

It is not surprising that treewidth and radius are related for drawings. A classical result of Robertson and Seymour [66, (2.7)] says that $\operatorname{tw}(G)\leqslant 3\operatorname{rad}(G)+1$ for every connected planar graph $G$. Several authors improved this bound as follows.

We now prove that if a planar graph $G$ has large treewidth, then the map graph of any plane drawing of $G$ has large radius. For a plane graph $G$, we say a graph $H$ is a triangulation of $G$ if $H$ is a plane supergraph of $G$ on the same vertex set and where each face is a triangle.

Note that a version of Lemma 7 with $\operatorname{rad}(M_{\_}G)$ replaced by the eccentricity of the outerface in $M_{\_}G$ can be proved via outerplanarity²²2Say a plane graph $G$ is $k$-outerplane if removing all the vertices on the boundary of the outerface leaves a $(k-1)$-outerplane subgraph, where a plane graph is $0$-outerplane if it has no vertices. Consider a plane graph $G$, where $v_{\_}{\infty}$ is the vertex of $M_{\_}G$ corresponding to the outerface. Then one can show that if $v_{\_}{\infty}$ has eccentricity $k$ in $M_{\_}G$, then $G$ is $(k+1)$-outerplane, and conversely, if $G$ is $k$-outerplane, then $v_{\_}{\infty}$ has eccentricity at most $k$ in $M_{\_}G$. Bodlaender [12] showed that every $k$-outerplanar graph has treewidth at most $3k-1$. The same proof shows that every $k$-outerplane graph has treewidth at most $3k-1$ (which also follows from [28])..

We use the following lemma about planarisations to extend Lemma 7 from plane drawings to arbitrary drawings.

We are now ready to prove Theorem 5.

The next lemma is a cornerstone of this paper. It shows that if the map graph of a circular drawing has large radius, then the crossing graph contains a useful substructure. For $a,b\in\mathbb{R}$ where $a<b$, let $(a,b)$ denote the open interval $\{r\in\mathbb{R}\colon a<r<b\}$.

This subsection studies the structure of graphs that have circular drawings whose crossing graph is (topological) $K_{\_}t$-minor-free. Much of our understanding of the structure of these graphs is summarised by the next four results (Theorems 3, 4, 10 and 11).

See 3

See 4

From these we may deduce a product structure theorem for graphs that have a circular drawing whose crossing graph is $K_{\_}t$-minor-free. For two graphs $G$ and $H$, the strong product $G\boxtimes H$ is the graph with vertex-set $V(G)\times V(H)$, and with an edge between two vertices $(v,w)$ and $(v^{\prime},w^{\prime})$ if and only if $v=v^{\prime}$ and $ww^{\prime}\in E(H)$, or $w=w^{\prime}$ and $vv^{\prime}\in E(G)$, or $vv^{\prime}\in E(G)$ and $ww^{\prime}\in E(H)$. Campbell et al. [16, Prop. 55] showed that if a graph $G$ is $K_{\_}{2,t}$-topological minor-free and has treewidth at most $k$, then $G$ is isomorphic to a subgraph of $H\boxtimes K_{\_}{\mathcal{O}(t^{2}k)}$ where $\operatorname{tw}(H)\leqslant 2$. Thus Theorems 3 and 4 imply the following product structure result.

En route to proving these results, we use the cycle structure built by Lemma 9 to find (topological) complete minors in the crossing graph of circular drawings. We first show that the treewidth and Hadwiger number of $X_{\_}D$ as well as the radius of $M_{\_}D$ are all linearly tied.