1 Introduction↩︎

The intersection graph of a finite family \(\mathcal{F}\) is the graph with vertex set \(\{v_A : A \in \mathcal{F}\}\) and edge set \(\{v_A v_B : A, B \in \mathcal{F}, \;A \cap B \neq \emptyset\}\). The boxicity of a graph \(G\), denoted by \(\mathop{\mathrm{box}}(G)\), is defined to be the minimum dimension \(d\) such that \(G\) can be represented as the intersection graph of a family of \(d\)-dimensional axis-parallel boxes in \(\mathbb{R}^d\). Boxicity was introduced in 1969 by Roberts Rob?. Its study was initially motivated by applications in ecology, specifically in modelling niche overlap and competition between species 1978_Cohen?, 1976_Roberts?. Further applications appear in operations research, where boxicity has been used in fleet maintenance and task assignment problems 1983_Cozzens?, 1981_Opsut?.

While graphs of boxicity one (i.e. interval graphs) can be recognized in linear time 1975_Kellogg?, even the decision problem of whether a graph has boxicity at most \(2\) is NP-hard 1994_Kratochvil_NP?. Consequently, significant effort has been directed towards relating boxicity to other graph parameters (e.g.ABC?, CS?, Esp?, EJ?) or computing it for specific graph classes (e.g.2023_Caoduro?, 2011_Chandran?, 1984_Scheinerman?, 1986_Thomassen?).

In 1983, Cozzens and Roberts 1983_Cozzens? initiated the study of boxicity from the perspective of covering the graph’s complement using co-interval graphs. Using this complement co-interval cover perspective, Cozzens and Halsey 1991_COZZENS_Coboxicity? proved that the decision problem of whether \(\mathop{\mathrm{box}}(G) \leq 2\) is polynomial when \(G\) is a co-comparability graph. Motivated by the potential of this covering perspective, we investigate directly the boxicity of graph complements. We refer to the boxicity of the complement of a graph \(G\) as its co-boxicity, denoted by \(\mathop{\mathrm{co-box}}(G)\). As \(\mathop{\mathrm{co-box}}(G) = \mathop{\mathrm{box}}(\overline{G})\), the general co-boxicity decision problem for \(k = 2\) is also NP-hard.

There are few known examples of graph classes for which the co-boxicity can be computed efficiently. An elementary example is the class of paths, where the path on \(n\) vertices has co-boxicity \(\left\lceil \frac{n-1}{3} \right\rceil\) 1983_Cozzens?. Yannakakis 1982_Yannakakis? proved that the decision problem is NP-hard for \(k=3\) for bipartite graphs. Following this result, a natural general problem to consider is to determine how far this efficiency on paths extends within the class of bipartite graphs. A good next candidate is the class of trees.

Beyond bipartite graphs, additional examples of graphs with efficiently computable co-boxicity include those with co-boxicity at most \(2\), such as co-block graphs and co-outerplanar graphs 1984_Scheinerman?. For such a graph, computing co-boxicity is equivalent to the linear-time decision problem of whether its complement is an interval graph 1975_Kellogg?. Adiga et al. 2010_Adiga? showed that the co-boxicity of graphs with bounded stable set number can be computed efficiently. More recently, Caoduro and Sebő 2023_Caoduro_GD? established that the co-boxicity of the line graph of the complete graph on \(n\) vertices is \(n-2\), and that for any fixed \(k\) there is a polynomial-time algorithm to decide whether the co-boxicity of a line graph is at most \(k\). They left as an open question whether this dependency on \(k\) can be removed 2023_Caoduro_GD?*Problem 2.

In this work, we expand the list of graph classes for which the co-boxicity can be computed in polynomial time to include block graphs. A block graph is a graph in which every maximal \(2\)-connected subgraph, called a block, is a complete graph. Since trees are block graphs, we answer Question [question:forest-coboxicity] affirmatively. Moreover, since line graphs of trees are also block graphs, our result provides partial progress towards resolving Question [question:line-graph-coboxicity]. We now state our main result.

Co-boxicity is closely related to another graph parameter called the threshold co-dimension. A threshold graph is either an isolated vertex, or it is obtained from another threshold graph by including an isolated or universal vertex (i.e. a vertex adjacent to all other vertices). Equivalently, a threshold graph is a \(\{P_4, C_4, 2K_2\}\)-free graph, where \(P_4\) is the path on four vertices, \(C_4\) is the cycle on four vertices, and \(2K_2\) is the disjoint union of two edges. A collection \(\{T_1, T_2, \ldots, T_k\}\) of threshold subgraphs of \(G\) is called a threshold cover of \(G\) if \(E(G) = \bigcup_{i=1}^k E(T_i)\). In this terminology, the threshold co-dimension of \(G\), denoted by \(\mathop{\mathrm{co-dim_{TH}}}(G)\), is defined to be the minimum size of a threshold cover of \(G\). Since \(K_2\) is a threshold graph, \(\mathop{\mathrm{co-dim_{TH}}}(G)\) is well-defined for all \(G\). The value \(\mathop{\mathrm{co-dim_{TH}}}(G)\) is also known as the threshold dimension of \(\overline{G}\). See 1975_chvatalAndHammer_thresholdDimIsNPHard?, 1995_Mahadev_book_thresholdGraphs? for background on the threshold dimension and its applications.

Chvátal and Hammer 1975_chvatalAndHammer_thresholdDimIsNPHard? proved that calculating \(\mathop{\mathrm{co-dim_{TH}}}(G)\) for a general graph is an NP-hard problem. Adapting the proof of Theorem 1, we show that when \(G\) is a block graph, \(\mathop{\mathrm{co-dim_{TH}}}(G)\) can be computed in polynomial time, and moreover that \(1\leq \tfrac{\mathop{\mathrm{co-dim_{TH}}}(G)}{\mathop{\mathrm{co-box}}(G)} \leq 2\) (see Proposition [proposition:threshold-co-dimension-and-co-boxicity-bounds]).

Our method for establishing Theorems 1 and 2 builds on techniques first introduced by Cozzens and Roberts 1983_Cozzens? and further developed by Caoduro and Sebő 2023_Caoduro_GD? to study co-boxicity using co-interval covers. In Section 2, we review these techniques along with structural properties of graph blocks that are relevant to our arguments. Our method first characterizes the class of maximal co-interval subgraphs of block graphs and then uses the tree-like structure of block graphs to design an algorithm that constructs a minimum co-interval cover. In Section 3, we characterize the maximal co-interval subgraphs of block graphs as big ants, which are generalizations of graphs known in the literature as ants 1983_Cozzens?. In Section 4, we present Algorithm 6, which yields a polynomial-time computation of the co-boxicity of block graphs, and we prove Theorem 1. The proof of Theorem 2 follows the same general approach, with only a few adjustments. These adjustments are provided in Section 5, where we also describe how Algorithm 6 can be adapted to compute the threshold co-dimension of block graphs in polynomial time. The method we develop to prove Theorems 1 and 2 not only establishes tractability for block graphs but also provides a framework that likely extends to other block-restricted classes, such as cactus graphs (i.e. graphs where each block is a cycle). We conclude in Section 6 with a discussion of these possible extensions and other open problems motivated by our approach.

2 Preliminaries↩︎

All graphs in this paper are simple. We use standard graph-theoretic notation throughout (see 2003_Schrijver? for background and terminology) and briefly recall here the notation used most frequently.

Let \(G = (V, E)\) be a graph. For a vertex \(v \in V\), the sets \(\delta_G(v) \subseteq E\) and \(N_G(v) \subseteq V\) are defined to be the edges incident to \(v\) and vertices adjacent to \(v\), respectively. The closed neighbourhood of \(v\) is defined as \(N_G[v] = N_G(v) \cup \{v\}\). The degree of a vertex \(v\) is denoted by \(d_G(v)\), and satisfies \(d_G(v) = |\delta_G(v)| = |N_G(v)|\). A subgraph of \(G\) is a graph \((U,F)\) satisfying \(U \subseteq V\) and \(F \subseteq E\). A subgraph \((U,F)\) is induced in \(G\) if for all \(u,v \in U\), \(uv \in F\) if and only if \(uv \in E\). The induced subgraph of \(G\) on a vertex set \(U \subseteq V\) is denoted by \(G[U]\). If \(U \subseteq V\) is a set of vertices to be removed from \(G\), then the induced subgraph \(G[V \setminus U]\) is denoted by \(G \setminus U\). Given two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\), if \(V_1 \cap V_2 = \emptyset\), then we refer to the graph \((V_1 \cup V_2, E_1 \cup E_2)\) as the disjoint union of \(G_1\) and \(G_2\). Note that any graph is the disjoint union of its connected components.

2.1 Co-interval graphs↩︎

A graph \(H = (U,F)\) is a co-interval graph if there exists a function \(I\) mapping \(U\) to closed intervals in the real line such that \(uv \in F\) if and only if \(I(u) \cap I(v) = \emptyset\). The function \(I\) is called a co-interval representation of \(H\). Another characterization of a co-interval graph can be expressed in terms of orderings of its vertices. For a positive integer \(n\), let \([n] = \{1,2,\ldots,n\}\). Given an ordering \(\sigma\) of the elements of a set of size \(n\) and an index \(i \in [n]\), we denote by \(\sigma(i)\) the \(i\)-th element of \(\sigma\).

Following the approach in 2023_Caoduro_GD?, vertex orderings can be used to study the co-interval subgraphs of a graph. To this end, for any graph \(G = (V,E)\) and any ordering \(\sigma\) of \(V\), we construct a subgraph of \(G\) satisfying Property (?? ) with respect to the restriction of \(\sigma\) to its vertex set.

We refer to a co-interval subgraph \(H\) of \(G\) as maximal if there does not exist a co-interval subgraph \(H'\) of \(G\) satisfying \(E(H) \subsetneq E(H')\). Since maximality refers only to the edge set, and the property of being a co-interval graph is preserved under the addition or removal of isolated vertices, we assume that a maximal subgraph does not contain isolated vertices. We conclude with the following lemma of Caoduro and Sebő, and provide another proof using our terminology.

2.2 Co-interval covers and co-boxicity↩︎

Let \(G=(V, E)\) be a graph with co-boxicity \(d\). Then, by the definition of co-boxicity, there is a family \(\mathcal{B} = \{B(u): u \in V\}\) of \(d\)-dimensional axis-parallel boxes in \(\mathbb{R}^d\) satisfying \(uv \in E\) if and only if \(B(u)\) and \(B(v)\) are disjoint. For each \(i \in [d]\), the projections of the boxes in \(\mathcal{B}\) onto the \(i\)-axis form a co-interval representation of a co-interval graph \(G_i\). Since two boxes in \(\mathcal{B}\) are disjoint if and only if there is an axis-aligned plane separating them, \(G_i\) is a subgraph of \(G\). Moreover, \(uv \in E\) if and only if there is an \(i \in [d]\) such that \(uv \in E(G_i)\).

A family \(\mathcal{C}= \{G_1, G_2, \ldots, G_k\}\) is a co-interval cover of \(G\) if \(\bigcup_{i\in[k]} E(G_i)=E\) and for each \(i \in [k]\), \(G_i\) is a co-interval subgraph of \(G\). So, if \(\mathcal{C}\) has minimum size, then \(\mathop{\mathrm{co-box}}(G) = |\mathcal{C}|\).

Co-interval graphs are easily seen to be hereditary by their co-interval representations, and they are \(\{2K_2\}\)-free because \(\overline{2K_2}=C_4\) is not an interval graph. So, no graph in a co-interval cover of \(G\) can have edges in more than one connected component. By Lemma 2, it follows that \(\mathop{\mathrm{co-box}}(G)\) equals the sum of the co-boxicities of the connected components of \(G\).

2.3 Block structure and near-leaf blocks↩︎

In this section, we examine the blocks of general graphs. A block of a graph \(G\) is a maximal \(2\)-connected component of \(G\). A vertex \(v\) of \(G\) is a cut-vertex if its removal increases the number of connected components of \(G\). Any two blocks of \(G\) share at most one vertex, and the shared vertex must be a cut-vertex. Two distinct blocks are neighbours if they share a common cut-vertex. We classify blocks as follows: a block is an isolated block if it contains no cut-vertex, a leaf block if it contains exactly one cut-vertex, and an internal block otherwise. A block with exactly \(2\) vertices is an edge block. If all leaf blocks in a graph \(G\) are edge blocks, then \(G\) is pointed.

The blocks and cut-vertices of a graph exhibit a tree-like incidence structure, called the block-cut tree 1966_Harary?. The following observation about the blocks of a connected graph mirrors the elementary fact that every tree with more than one vertex has a leaf vertex.

We now introduce a subclass of internal blocks that play an essential role in our method.

Near-leaf blocks exist whenever internal blocks exist. We prove this using the following graph operation. The core of a graph \(G\), denoted by \(\rho(G)\), is the graph obtained from \(G\) by removing \(V(Q)\) for each isolated block \(Q\), and \(V(Q')\setminus\{u\}\) for each leaf block \(Q'\) with cut-vertex \(u\).

The following lemma provides a sufficient condition for the existence of near-leaf blocks.

3 Maximal co-interval subgraphs of block graphs↩︎

Recall from Section 2.2 that the co-boxicity of a graph can be computed by finding a minimum co-interval cover. A key step in our covering approach is to identify the maximal co-interval subgraphs.

Ants are a class of co-interval graphs originally used in the context of co-boxicity in 1983_Cozzens? to construct co-interval covers. Given an edge \(uv\) of a graph \(G\), the \((u,v)\)-ant subgraph of \(G\) is \((N_G[u] \cup N_G[v], \delta_G(u) \cup \delta_G(v))\). The following definition of big ants generalizes ants by replacing the specified edge with a possibly larger clique. Then in Lemma 7, we will show that big ants are also co-interval graphs. As the blocks of a block graph are cliques, big ants can produce smaller co-interval covers of block graphs than ants can.

Now we establish that every maximal co-interval subgraph of a block graph is a big ant.

4 Covering block graphs with big ants↩︎

In this section, we prove Theorem 1. Given a block graph \(G\), Algorithm 6 produces a minimum cover \(\mathcal{C}\) of \(G\) using big ants in polynomial time. By Lemma 7, big ants are co-interval graphs, so \(\mathcal{C}\) is also a minimum co-interval cover of \(G\). Thus, by Lemma 2, we have \(|\mathcal{C}| = \mathop{\mathrm{co-box}}(G)\).

Algorithm 6 processes a connected component of the graph in each iteration. If the component is a clique or star, then it is a big ant. Otherwise, the algorithm leverages the tree-like block structure of graphs to efficiently identify a leaf block with at least \(3\) vertices or a near-leaf block. Then, since the blocks in block graphs are cliques, this block can be covered using a big ant that extends it.

We structure the proof of Theorem 1 in two parts. Section 4.1 shows that Algorithm 6 terminates in polynomial time and Section 4.2 proves that it returns a minimum co-interval cover.

4.1 Algorithm 6 is polynomial↩︎

We establish that Algorithm 6 terminates in a number of steps that is polynomial in the size of the input. First, we show that the algorithm terminates. At the beginning of each iteration, a connected component \(H\) of the residual graph \(\Gamma\) is selected so that \(E(H) \neq \emptyset\). Then the algorithm proceeds differently based on the structure of \(H\). If \(H\) is a clique or a star, then Case [it:case1] applies and \(V(H)\) is removed from \(\Gamma\). If \(H\) is not a clique, then since \(H\) is a block graph, it is not an isolated block, and so by Lemma 4, it contains a leaf block. If \(H\) contains a leaf block \(Q\) satisfying \(|V(Q)| \geq 3\), then Case [it:case2] applies and \(V(Q)\) is removed from \(\Gamma\). If Cases [it:case1] and [it:case2] do not apply, then \(H\) is pointed in Case [it:case3]. By Lemma 6, \(H\) contains a near-leaf block \(Q\). Then, depending on the number of cut-vertices in \(Q\), a subset of \(V(Q_{u,w})\) is removed from \(\Gamma\). In each case of the while-loop, at least one vertex of \(H\) is removed. Since \(H\) has no isolated vertices, at least one edge is removed from \(\Gamma\).

Now we show that Algorithm 6 is polynomial. At each iteration, the algorithm identifies a connected component \(H\) with at least one edge, checks its structural type, and then selects an appropriate block to process. These operations rely on computing the blocks and cut-vertices of the graph, which can be done in polynomial time using standard techniques 1971_Paton?. Once the block structure is known, detecting whether \(H\) contains a near-leaf block and identifying one only requires local inspection of the block-cut tree. Moreover, constructing the big ant to add to \(\mathcal{C}\) and updating \(\Gamma\) involve operations on blocks, which can also be implemented efficiently. Therefore, since Algorithm 6 terminates in a polynomial number of iterations, each of which can be performed in polynomial time, the total running time is polynomial in the size of the input graph.

4.2 Algorithm 6 returns a minimum co-interval cover↩︎

Let \(G\) be a block graph, and let \(\mathcal{C}\) be the family of big ants returned by Algorithm 6 applied to \(G\). Consider one iteration of the while-loop of Algorithm 6, and let \(H\) be a connected component of the residual graph \(\Gamma\). Moreover, let \(R\) be the vertex set removed from \(\Gamma\) at the end of the iteration. The definition of \(R\) depends on which case we are considering: \(R\) equals \(V(H)\), \(V(Q)\), and \(V(Q_u)\) in Cases [it:case1], [it:case2], and [it:case3](a), respectively, and in Case [it:case3](b) we have \[R = \begin{cases} V(Q_{u,w})\setminus \{v\} &\text{Q contains exactly 3 cut-vertices;} \\ S^u \cup S^w \cup \{u,w\} &\text{otherwise.} \end{cases}\] For each iteration of the while-loop of Algorithm 6, the following lemmas hold.

As big ants are co-interval graphs by Lemma 7, Lemma 9 implies that \(\mathcal{C}\) is a co-interval cover of \(G\). Moreover, by Lemma 3, we have that \(\mathop{\mathrm{co-box}}(\Gamma) = \mathop{\mathrm{co-box}}(\Gamma \setminus V(H)) + \mathop{\mathrm{co-box}}(H)\). Thus, Lemma 10 implies that \(\mathop{\mathrm{co-box}}(\Gamma)\) decreases by at least one by the end of each iteration of the while-loop. Since the size of \(\mathcal{C}\) increases by one after each iteration, we have \(|\mathcal{C}| \leq \mathop{\mathrm{co-box}}(G)\). Additionally, as \(\mathcal{C}\) is a co-interval cover of \(G\), we have \(|\mathcal{C}| \geq \mathop{\mathrm{co-box}}(G)\). Therefore, we conclude that \(|\mathcal{C}| = \mathop{\mathrm{co-box}}(G)\), and so Algorithm 6 returns a minimum co-interval cover of \(G\).

We now turn to the proofs of Lemmas 9 and 10.

5 Threshold co-dimension of block graphs↩︎

In this section, we prove Theorem 2. We adapt the approach we used to prove Theorem 1. As a first step, we establish two lemmas analogous to Lemmas 7 and 8 for threshold graphs.

Cliques are threshold graphs since they can be constructed by successively adding universal vertices. Similarly, a big ant \(Q_u\) has a threshold graph construction: begin with the clique \(Q \setminus \{u\}\), add the remaining neighbours of \(u\) as isolated vertices, and finally add \(u\) as a universal vertex.

Note that for distinct vertices \(u,v\) in which both \(u\) and \(v\) have neighbours outside of \(Q\), the big ant \(Q_{u,v}\) is not a threshold graph because it contains a \(P_4\) as an induced subgraph. A characterization of the maximal threshold subgraphs of a block graph as big ants of the form \(Q_u\) follows from Lemma 8.

Now, Algorithm 6 can be adjusted to compute the threshold co-dimension of a block graph by replacing Case [it:case3] with Case 8 stated below.

The proof of Theorem 2 is analogous to that of Theorem 1, requiring only minor adjustments to account for the shift from the co-interval to the threshold framework, together with the assumption \(w = u\), which distinguishes Case 8 from Case [it:case3]. We therefore omit the details of the proof.

We conclude this section with a description of the relationship between co-boxicity and threshold co-dimension. It is well-known that for any graph \(G\), \(\mathop{\mathrm{co-box}}(G) \leq \mathop{\mathrm{co-dim_{TH}}}(G)\) 2025_Francis?*Observation 6. In general, the threshold co-dimension of a graph cannot be upper-bounded by a function of its co-boxicity. For example, \(G = K_{n/2,n/2}\) is a co-interval graph satisfying \(\mathop{\mathrm{co-dim_{TH}}}(G) = n/2\) (see 2025_Francis?*Proposition 8). However, for block graphs, these two parameters are close together.

6 Discussion↩︎

Algorithm 6 illustrates how co-boxicity can be computed by combining two key ingredients: (1) the block-cut tree, which provides an ordering that guides the cover construction through leaf and near-leaf blocks; and (2) a structural characterization of the maximal co-interval subgraphs of the class under consideration. For block graphs, Lemma 8 shows that these maximal subgraphs are precisely big ants, enabling a polynomial algorithm for both co-boxicity and threshold co-dimension.

This method suggests a general approach. For other block-restricted graph classes, if one can characterize the maximal co-interval subgraphs of the blocks and then minimally cover them, then the block-cut tree can perhaps be leveraged to design efficient covering algorithms. The key step that enables this generalization is found in the proof of Lemma 8, which shows that the maximal co-interval subgraphs of any graph are contained in one of the graphs 3 or 4 . Both of these graphs resemble a big ant, except that they extend an entire block instead of a clique. Cactus graphs, in which all blocks are cycles, provide a natural test case, and more generally, classes with blocks drawn from highly constrained classes (e.g. strongly regular graphs) may also be tractable.

Beyond block-restricted classes, an interesting setting arises when ants are the maximal co-interval subgraphs. A large graph class with this property is the class of graphs with girth (i.e. length of a shortest cycle) at least \(5\). Note that for any graph \(G = (V,E)\) with girth at least \(5\), for any ordering \(\sigma\) of \(V\) with \(u_\sigma = \sigma(1)\), \(V_2^{\sigma}\) contains at most one vertex \(v_\sigma\), and so \(G^{\sigma}\) is a subgraph of the \((u_\sigma,v_\sigma)\)-ant. Thus, every maximal co-interval subgraph of \(G\) is an ant. Now, there are at most \(|E|\) maximal co-interval subgraphs of \(G\), each a \((u,v)\)-ant for some edge \(uv \in E\). From this, we can decide whether \(\mathop{\mathrm{co-box}}(G) \leq k\) in \(\mathcal{O}(|E|^k)\) time, and so the co-boxicity decision problem is polynomial. However, it is not known whether computing \(\mathop{\mathrm{co-box}}(G)\) is a polynomial problem. We remark that a greedy approach in which edge-maximizing ant subgraphs are selected is not sufficient, even when \(G\) is a tree. Indeed, a strategy to order the ant subgraphs of trees using near-leaf blocks was shown to be necessary in the proof of Theorem 1.

Another natural class to consider is the class of outerplanar graphs, which are graphs with a planar embedding such that all vertices are incident to the outer face. The dual of the inner faces of an outerplanar embedding forms a tree, distinct from the block-cut tree of the graph. The maximal co-interval subgraphs of outerplanar graphs have not been characterized in general. However, the tree structure of the inner faces might be leveraged to construct minimum co-interval covers. A good first step is to consider the subclass of outerplanar graphs with girth at least \(5\).

6.0.1 ↩︎

The authors are grateful to Amna Adnan, Matthew Barclay, Josh Childs, and the coordinators of the Pacific Institute for the Mathematical Sciences (PIMS) VXML program for initiating this research collaboration. M. Caoduro was supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant [RGPIN-2021-02475]. W. Evans was supported by NSERC Discovery Grant RGPIN-2022-04449. We gratefully acknowledge that this research was supported in part by PIMS.