Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs

Abstract

We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called $B_0$-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal $B_0$-VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of $B_0$-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for $B_0$-VPG graphs in the class of block graphs.

1 Introduction

A VPG representation of a graph G is a collection of paths of the two-dimensional grid where the paths represent the vertices of G in such a way that two vertices of G are adjacent in G if and only if the corresponding paths share at least one vertex of the grid. A graph which has a VPG representation is called a VPG graph. In this paper, we consider the subclass $B_0$-VPG.

A $B_0$-VPG representation of G is a VPG representation in which each path in the representation is either a horizontal path or a vertical path on the grid. A graph is a $B_0$-VPG graph if it has a $B_0$-VPG representation. Thus, a $B_0$-VPG graph is the intersection graph of zero bend paths on a grid.

The class of $B_0$-VPG graphs form a subclass of the well-known segment graphs, or intersection graphs of straight-line segments in the plane. Indeed, the class of k-DIR graphs has been defined as the class of segment graphs in which the straight-line segments lie in at most k directions [7]. Therefore, it is easy to see that $B_0$-VPG graphs are equivalent to 2-DIR graphs.

Representations by intersections of paths on grids arise naturally in the context of circuit layout problems and layout optimization [9] where a layout is modelled as paths (wires) on a grid. Often one seeks to minimize the number of times a wire is bent [3, 8] in order to minimize the cost or difficulty of production. Other times layout may consist of several layers where the wires on each layer are not allowed to intersect. This is naturally modelled as the coloring problem on the corresponding intersection graph.

The recognition problem is NP-complete for both VPG and $B_0$-VPG graphs (see [1] for more details about this and related results). Since all interval graphs are $B_0$-VPG graphs, it is natural to consider other subclasses of chordal $B_0$-VPG graphs. In [5], certain subclasses of $B_0$-VPG graphs have been characterized and shown to admit a polynomial time recognition; namely split, chordal claw-free and chordal bull-free $B_0$-VPG graphs. Recently, in [4] the authors present a polynomial time algorithm for deciding whether a given chordal graph is a $B_0$-VPG graph. In [1], it was shown that chordal $B_0$-VPG graphs are equivalent to the strongly chordal $B_0$-VPG graphs.

In this paper, we consider $B_0$-VPG graphs more from a structural point of view. We present a minimal forbidden induced subgraph characterization of $B_0$-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative recognition and representation algorithm for $B_0$-VPG graphs in the class of block graphs.

2 Preliminaries

In this paper all graphs are connected, finite and simple. We use the notation that was used by Bondy and Murty [2].

Let $G=(V,E)$ be a graph with vertex set V and edge set E. For a graph G, let |G| denote the cardinality of V(G).

We write $G-v$ for the subgraph obtained by deleting a vertex v and all the edges incident to v. Similarly, for $A\subseteq V$, we denote by $G-A$ the subgraph of G obtained by deleting the vertices in A and all the edges incident to them, that is, $G-A=G[V\backslash A]$.

If H is a graph, a graph G is H-free if G contains no induced subgraph isomorphic to H. If $\mathcal H$ is a collection of graphs, the graph G is $\mathcal H$-free if G is H-free for every $H\in \mathcal H$.

A clique is a set of pairwise adjacent vertices which is maximal under inclusion. A thin spider $N_n$ is the graph whose 2n vertices can be partitioned into a clique $K=\{c_1,\ldots c_n\}$ and a set $S=\{s_1,\ldots ,s_n\}$ of pairwise nonadjacent vertices such that, for $1\le i,j\le n$, $s_i$ is adjacent to $c_j$ if and only if $i=j$. We say that $N_n$ is a thin spider of size n.

It was proved by Golumbic and Ries [5] that the thin spider $N_5$ is not $B_0$-VPG.

The following lemma will be used in our paper.

Lemma 1

 [1] In a $B_0$-VPG representation of a clique, all the corresponding paths share a common grid point.

We will distinguish between two types of $B_0$-VPG representations of a clique: a line clique and a cross clique. We say that a clique is represented as a line clique if all paths corresponding to the vertices of the clique use a common row or a common column and intersect on at least one grid point of that row or column. A clique is said to be represented as a cross clique if the paths corresponding to the vertices of the clique share exactly one grid point, say $(x_i,y_j)$, and there exists at least one such path which uses column $x_i$ and at least one such path which uses row $y_j$. The grid point $(x_i,y_j)$ is called the center of the cross clique (see Fig. 1 for examples). It was observed in [5] that any $B_0$-VPG representation of a clique is either a line clique or a cross clique.

Fig. 1

A line clique and a cross clique

3 Block Graphs

In this section we will give a characterization of $B_0$-VPG graphs restricted to block graphs by a family of minimal forbidden induced subgraphs.

A block graph is a connected graph in which every two-connected component (block) is a clique. A diamond is a graph obtained from $K_4$ by deleting exactly one edge. A graph is called chordal if it does not contain any chordless cycle of length at least four. It is known that block graphs are connected chordal diamond-free graphs.

A cutpoint is a vertex whose removal from the graph increases the number of connected components.

Let G be a block graph. An endblock is a block having exactly one cutpoint. An almost endblock is a block B having at least two cutpoints and such that exactly one of these cutpoints belongs to blocks (different from B) that are not endblocks. An internal block is a block that is neither an endblock nor an almost endblock.

We denote by 3-cutpoint a cutpoint that belongs to exactly three blocks, and by 2-cutpoint a cutpoint that belongs to exactly two blocks, one of which is an endblock.

The block-cutpoint-tree bc(G) of a graph G, introduced by Harary and Prins in [6], is a graph whose vertices are in one-to-one correspondence with the blocks and cutpoints of G, and such that two vertices of bc(G) are adjacent if and only if one corresponds to a block H of G and the other to a cutpoint c of G, and c is in H.

Let ${\mathcal {F}}$ denote the family of block graphs obtained from $N_5$ by a finite sequence of applications of the following procedure: consider a complete subgraph of size 4 having at least two 2-cutpoints, say $v_1$ and $v_2$, with endblocks $B_1$ and $B_2$, respectively. Contract $v_1$ and $v_2$ into a single vertex x. Then, replace $B_1 -\{x\}$ and $B_2 - \{x\}$ by two thin spiders of size 3, making x adjacent to the vertices of the cliques of both the spiders. In Fig. 2 we offer some examples of graphs in ${\mathcal {F}}$.

Fig. 2

Some examples of graphs in ${\mathcal {F}}$. In the figure, v is a cutpoint, A is an endblock, B is an almost endblock, and C is an internal block

Proposition 2

A graph in ${\mathcal {F}}- \{N_5\}$ has the following properties:

• (i) each block is of size at most 4;

• (ii) all the vertices are either leaves, 2-cutpoints or 3-cutpoints;

• (iii) the endblocks are of size 2 and have a 2-cutpoint;

• (iv) the almost endblocks are of size 4 and have three 2-cutpoints and one 3-cutpoint;

• (v) the internal blocks are of size 3 and have one 2-cutpoint and two 3-cutpoints;

• (vi) a graph in ${\mathcal {F}}$ obtained from $N_5$ by applying the procedure k times, $k \ge 1$, has $6(k+1)$ blocks ($4(k+1)+1$ endblocks, $k+2$ almost endblocks, and $k-1$ internal blocks), $5(k+1)$ cutpoints (k 3-cutpoints and $4(k+1)+1$ 2-cutpoints), and $9(k+1)+1$ vertices.

Proof

We will prove it by induction on the number of times we apply the procedure. By symmetry of $N_5$, there is only one graph obtained by applying the procedure once (Fig. 2b), and it has no internal blocks. It is easy to verify that this graph satisfies the properties claimed.

Suppose the properties are satisfied by all graphs in ${\mathcal {F}}$ obtained from $N_5$ by applying the procedure k times, $k \ge 1$, and let G be one such graph. Let us apply the procedure once more. Let H be a complete subgraph of size 4 in G. By the inductive hypothesis, H is an almost endblock of G, and has three 2-cutpoints and one 3-cutpoint. By Proposition 2.(iii), the blocks incident to the 3-cutpoint are not endblocks.

Choose two vertices $v_1$ and $v_2$ which are 2-cutpoints, and let $B_1$ and $B_2$ be the endblocks incident with $v_1$ and $v_2$, respectively. By Proposition 2.(iii), $B_1$ and $B_2$ are of size 2. Contract $v_1$ and $v_2$ into a single vertex x, and replace $B_1 - \{x\}$ and $B_2 - \{x\}$ by two thin spiders of size 3, induced respectively by the vertices $\{c_1,c_2,c_3,s_1,s_2,s_3\}$ and $\{c'_1,c'_2,c'_3,s'_1,s'_2,s'_3\}$, making x adjacent to the vertices of the cliques of both the spiders, i.e, $\{c_1,c_2,c_3,c'_1,c'_2,c'_3\}$.

After the procedure, $H' = H -\{v_1,v_2\} \cup \{x\}$ is a block of size 3, and it has two 3-cutpoints and still one 2-cutpoint. The new blocks $\{c_1,c_2,c_3,x\}$ and $\{c'_1,c'_2,c'_3,x\}$ are almost endblocks, they are of size 4 and have three 2-cutpoints and one 3-cutpoint, namely x. And since the blocks incident to the other 3-cutpoints of $H'$ are not endblocks, $H'$ is an internal block. The six new endblocks $\{c_i,s_i\}$ and $\{c'_i,s'_i\}$, $i=1,2,3$ have a 2-cutpoint each (vertices $c_i$ and $c_i'$) and a leaf each (vertices $s_i$ and $s_i'$). The remaining blocks, as well as their conditions, are not affected. So Proposition 2.(i–v) are satisfied by the new graph. To see Proposition 2.vi, notice that we have replaced 2 endblocks by 8 new blocks, 6 of which are endblocks and 2 of which are almost endblocks. Also, one almost endblock has become an internal block. We have replaced 4 vertices by 13 vertices and, in particular, two 2-cutpoints by one 3-cutpoint and six 2-cutpoints. $\square$

Corollary 3

The family ${\mathcal {F}}$ is countably infinite.

Proof

By Proposition 2, for every graph in ${\mathcal {F}}$ there is always an almost endblock on which we can perform the procedure in order to obtain a new graph in ${\mathcal {F}}$ with strictly more vertices. $\square$

Corollary 4

Each graph in ${\mathcal {F}}$ is minimal, i.e., it does not contain another graph in ${\mathcal {F}}$ as an induced subgraph.

Proof

Let $G \in {\mathcal {F}}$ and let $G'$ be a proper connected induced subgraph of G. The blocks of $G'$ are the blocks of G intersected with $V(G')$. Suppose $G' \in {\mathcal {F}}$, and suppose $B'$ is a block of $G'$ such that $B' = B \cap V(G')$, with B a block of G, and $|B'| < |B|$. Then, B cannot be an endblock of G because, by Proposition 2.(iii), endblocks of G have size 2 and $|B'| < |B|$; $B'$ cannot be an almost endblock of $G'$ because by Proposition 2.(i) B has at most 4 vertices, and by Proposition 2.(iv) $B'$ should have 4 vertices; $B'$ cannot be an internal block of $G'$ because, in that case, by Proposition 2 and the cardinalities of each type of block, B should be an almost endblock but, by Proposition 2.(v), $B'$ should have two 3-cutpoints while B has only one 3-cutpoint, and no 2-cutpoint of G may become a 3-cutpoint in an induced subgraph of it. So, $B'$ is an endblock and B is either an almost endblock or an internal block. Let x be the cutpoint of $B'$ in $G'$. By Proposition 2.(iii), x is a 2-cutpoint of $G'$. If x is a 2-cutpoint in G, as B is not an endblock, we have that $G' = P_3$, and it does not belong to ${\mathcal {F}}$ (by Proposition 2.(vi)). If x is a 3-cutpoint in G, let $B_1$ and $B_2$ be the other two blocks in G that contain x. Since x is a 2-cutpoint in $G'$, the intersection of one of these blocks with $V(G')$ is $\{x\}$. Without loss of generality, suppose this is the case of $B_2$. If $B_1$ is an almost endblock in G, then $G'$ is an induced subgraph of the thin spider $N_4$, that is not in ${\mathcal {F}}$ (by Proposition 2.(vi)). If $B_1$ is an internal block, by cardinality, it may be either an endblock or an internal block in $G'$. In the first case, $G' = P_3$, that is not in ${\mathcal {F}}$. The second case cannot arise, because $B_1$ cannot have two 3-cutpoints in $G'$ (no 2-cutpoint of G may become a 3-cutpoint in an induced subgraph of it). $\square$

We will prove now some properties about the $B_0$-VPG representations of block graphs.

Lemma 5

If a clique K of a block graph G has at least three cutpoints, then, in any $B_0$-VPG representation of G, it has to be represented as a cross clique.

Proof

Let $v_i$, $1\le i\le 3$, be three of the cutpoints of K. Since $v_i$, $1\le i\le 3$, are cutpoints there exist vertices $x_j$, $1\le j\le 3$, such that $v_i$ is adjacent to $x_j$ if and only if $i=j$. Suppose that the clique K is represented as a line clique. Without loss of generality, we can assume that all the paths that represent vertices of K are horizontal paths using a common row of the grid. Suppose that $P_{v_1}$ is the farthest line in the East direction (by farthest line in some direction, in the context of a clique whose paths intersect at point p of the grid, we mean the path belonging to the clique and such that one of its endpoints maximizes the distance to p in that direction) and $P_{v_2}$ is the farthest line using the West. But, $P_{v_3}$ is a horizontal path lying in the same row that $P_{v_1}$ and $P_{v_2}$ and it has to be adjacent to $P_{x_3}$, and $P_{x_3}$ is not adjacent with $P_{v_1}$ and $P_{v_3}$. So, it is impossible to represent $P_{x_3}$. $\square$

Lemma 6

If a clique K of a block graph G has four cutpoints, then, in any $B_0$-VPG representation of G, the four cutpoints are represented as the farthest lines South, North, West and East, respectively. Similarly, if a clique K has three cutpoints, then they are represented as the farthest lines of any three different cardinal points.

Proof

Suppose that K has four cutpoints. By Lemma 5, K has to be represented as a cross clique. Using the same idea that in the proof of Lemma 5, it is easy to see that the four cutpoints are represented as the farthest lines South, North, West and East, respectively.

In a similar way, it is easy to see that the result follows if K has three cutpoints. $\square$

Lemma 7

In any $B_0$-VPG representation of the graph W, given in Fig. 3, the intersection points of the cliques $C_1$, K, and $C_2$ lie in a same line of the grid, and the intersection point of the clique K lies between the intersection points of the cliques $C_1$ and $C_2$.

Proof

Let $x_1$, $x_2$, $x_3$ be the intersection points in the grid of the cliques $C_1$, K, $C_2$, respectively. Suppose, by the contrary, that there is a $B_0$-VPG representation of the graph W such that $x_2$ does not lie between $x_1$ and $x_3$. Without loss of generality, we can assume that $x_2$ is to the left of $x_1$ and $x_3$. By Lemmas 6 and 5, since $C_1$ and $C_2$ have four cutpoints, they are represented as cross cliques where the four cutpoints are the farthest lines South, North, West and East, respectively. So, it is impossible to represent the vertex w of W. $\square$

Remark 1

Observe that all the graphs in ${\mathcal {F}}- \{N_5\}$ have W as an induced subgraph.

Proof

Let G be a graph in ${\mathcal {F}}- \{N_5\}$. Then G is obtained from a graph in ${\mathcal {F}}$ by the following procedure: consider a complete subgraph $B_0$ of size 4 having at least two 2-cutpoints, say $v_1$ and $v_2$, with endblocks $B_1$ and $B_2$, respectively. Contract $v_1$ and $v_2$ into a single vertex x. Then, replace $B_1 -\{x\}$ and $B_2 - \{x\}$ by two thin spiders of size 3, making x adjacent to the vertices of the cliques of both the spiders. The graph G has W as an induced subgraph, where the vertex labeled v in Fig. 3 is the vertex x, the vertex labeled w in Fig. 3 is a vertex of $B_0$ different from $v_1$ and $v_2$ (recall that $B_0$ has at least four vertices), and the remaining vertices in Fig. 3 are the vertices of the two thin spiders of size 3. $\square$

Fig. 3

The graph W and a $B_0$-VPG representation of it

Lemma 8

The graphs of ${\mathcal {F}}$ are not $B_0$-VPG.

Proof

The graph $N_5$ is not $B_0$-VPG [5]. We will proceed by induction on the number of applications of the procedure in the construction of the graph from $N_5$. Assume that if we applied the procedure k times, then we obtain a graph of ${\mathcal {F}}$ which is not $B_0$-VPG.

Let G be a graph of ${\mathcal {F}}$ which is obtained applying the procedure $k+1$ times. Suppose, on the contrary, that $G\in B_0$-VPG. We take a $B_0$-VPG representation of G.

By Remark 1, G has W as an induced subgraph. Let v be the vertex of W as in Fig. 3, let $P_v$ be the path which represents v in the $B_0$-VPG representation of G that we took. Let $x_1$, $x_2$, $x_3$ be the intersection points in the grid of the cliques $C_1$, K, $C_2$, respectively. Clearly, the three vertices lie in a same line of the grid and, by Lemma 7, $x_2$ lies between $x_1$ and $x_3$.

We are going to construct a new $B_0$-VPG representation. This is obtained from the previous one by removing the paths which correspond to $C_1$, $C_2$ and their corresponding endblocks; and adding the paths $P_{v_i}$, with $1\le i\le 4$, such that $V(P_{v_1})=\{x_1,x_2\}$, $V(P_{v_2})=\{x_2,x_3\}$, $V(P_{v_3})=\{x_1\}$ and $V(P_{v_4})=\{x_3\}$. Observe that this is a $B_0$-VPG representation of a graph of ${\mathcal {F}}$ that was obtained applying the procedure k times, which is a contradiction.

Hence, the graphs of ${\mathcal {F}}$ are not $B_0$-VPG. $\square$

We will prove the following theorem:

Theorem 9

Let G be a block VPG graph. Then G is $B_0$-VPG if and only if G is ${\mathcal {F}}$-free. Moreover, the graphs of ${\mathcal {F}}$ are minimal not $B_0$-VPG.

Proof

The “only if” part follows from Lemma 8. For the “if” part, let G be a block ${\mathcal {F}}$-free graph. Let s be a BFS ordering of the vertices of the block-cutpoint-tree bc(G), in such a way that $s_1$ is a vertex of bc(G) corresponding to a block of G. Let $H_i$ be the i-th block in s. We will consider the graph $G_i$ as the graph induced by the first i blocks $H_1,\ldots , H_i$ in s, and proceed by induction on i. Notice that the graph $G_i$ is connected and that $H_i$ is an endblock of $G_i$; moreover, by the BFS algorithm, if $i>1$, there is only one cutpoint c of G belonging to $H_i$ and appearing in s before $H_i$. We will denote that cutpoint as c(i). Notice that c(i) is a cutpoint of $G_i$. All the blocks between c(i) and $H_i$ containing c(i) are endblocks of $G_i$ and are consecutive in s. For each such block $H_j$, it holds $c(j)=c(i)$.

For each cutpoint c of G, there is only one block containing c and appearing before c in s. We will denote that block by $H^c$.

We will label the cutpoints of G as A or B, according to some rules, in decreasing order with respect to s. As s was obtained by a BFS of bc(G), if the cutpoint c is being labeled, all the other cutpoints of the blocks containing c and different from $H^c$ are already labeled. The cutpoint c will be labeled B if it belongs to at least two blocks, different from $H^c$, such that each of them either has at least four cutpoints or has exactly three cutpoints and one of them is already labeled B. The cutpoint c will be labeled A otherwise.

We will show by induction on i that we can find a $B_0$-VPG representation of $G_i$ such that if c is a cutpoint of G that is a vertex of $G_i$, then it corresponds to the farthest North, South, East or West line of the line or cross representation of the clique $H^c$ and, moreover, if c is labeled B, then it corresponds to the farthest North and South, or East and West (simultaneously) line of the line or cross representation of the clique $H^c$.

Claim. If G is ${\mathcal {F}}$-free, then the following conditions hold: (i) no block of G has five (or more) cutpoints; (ii) a cutpoint c labeled B belongs to exactly two blocks, different from $H^c$, such that each of them either has at least four cutpoints or has exactly three cutpoints and one of them (different from c) is labeled B; (iii) if a cutpoint c is labeled B, then $H^c$ has at most three cutpoints; and (iv) no block of G having at least three cutpoints is $H^{c_1}$ and $H^{c_2}$ for two cutpoints $c_1$ and $c_2$ labeled B.

Proof of the claim. Condition (i) holds since G is $N_5$-free. Let us assume from now on that (i) is satisfied.

Suppose, for the sake of contradiction, that one of conditions (ii), (iii) or (iv) does not hold. We will prove, by induction on the number of cutpoints labeled B on bc(G), that G contains a member of ${\mathcal {F}}$ as an induced subgraph.

If there is only one vertex v labeled B, then the conditions that should fail are (ii) or (iii). By the labeling rules and since v is the only vertex labeled B, it belongs to at least two blocks, different from $H^v$, such that each of them has four cutpoints. Either if the number of such blocks is at least three or if $H^v$ has four cutpoints, then G contains the second graph in Fig. 2 as an induced subgraph.

Suppose that the number of vertices labeled B is greater than one, and let v be the first vertex labeled B in the BFS sequence s (i.e., the one with higher index in s).

By the labeling rules and since v is the first vertex labeled B, it belongs to at least two blocks, different from $H^v$, such that each of them has four cutpoints. Either if the number of such blocks is at least three or if $H^v$ has four cutpoints, G contains the second graph in Fig. 2 as an induced subgraph. Assume then that v belongs to exactly two blocks, different from $H^v$, such that each of them has four cutpoints, and that $H^v$ has at most three cutpoints.

If $H^v$ has three cutpoints, let w be another cutpoint of G such that $H^v = H^w$. If w is labeled B, since s is a BFS order and v is the first vertex labeled B, w belongs to at least two blocks, different from $H^v$, such that each of them has four cutpoints. Then G contains the third graph in Fig. 2 as an induced subgraph. If w is labeled A, conditions (ii)–(iv) are “locally” satisfied by v, w, and $H^v$. We can replace v and all the connected components of $G - v$, except the one containing $H^v-v$, by four vertices $v_1$, $v_2$, $v_1'$ and $v_2'$ by making $v_1$ and $v_2$ adjacent to each other and to $H^v-v$, $v_1'$ adjacent just to $v_1$, and $v_2'$ adjacent just to $v_2$. Call $G'$ the obtained graph. Now the block $H' = H^v-v \cup \{v_1,v_2\}$ of $G'$ has four cutpoints (all of them labeled A), so the label of every cutpoint placed before v in s remains unchanged in a labeling of $bc(G')$, and the condition among (ii)–(iv) that was violated in G is still violated in $G'$. Since all cutpoints of $H'$ are labeled A, $G'$ has one less cutpoint labeled B than G. By the inductive hypothesis, $G'$ contains a graph F of ${\mathcal {F}}$ as an induced subgraph. Notice that $G' - \{v_1,v_1'\}$ and $G' - \{v_2,v_2'\}$ are isomorphic to an induced subgraph of G. So, since F is connected, if F does not contain one of $\{v_1,v_2\}$, then G contains F as an induced subgraph. If F contains $v_1$ and $v_2$, by Proposition 2, F contains $H' \cup \{v_1',v_2'\}$, and $H'$ is an almost endblock of F. Let $F'$ be the graph obtained from F by applying the procedure given in the definition of ${\mathcal {F}}$ to the vertices $v_1$ and $v_2$. Then $F'$ belongs to ${\mathcal {F}}$ and $F'$ is an induced subgraph of G.

If $H^v$ has two cutpoints, conditions (ii)–(iv) are “locally” satisfied by v and $H^v$, and the label of the other cutpoint of $H^v$ does not depend on the block $H^v$. We can delete from G all the connected components of $G - v$, except the one containing $H^v-v$, and call $G'$ the obtained graph. The block H is now an endblock of $G'$, the label of every cutpoint placed before v in s remains unchanged in a labeling of $bc(G')$, and the condition among (ii)–(iv) that was violated in G is still violated in $G'$. Moreover, v is no longer a cutpoint in $G'$, so $G'$ has one less cutpoint labeled B than G. By the inductive hypothesis, $G'$ contains a graph F of ${\mathcal {F}}$ as an induced subgraph. Since $G'$ is an induced subgraph of G, so is F. $\diamondsuit$

As a block H is $H^c$ for all but at most one of its cutpoints c, item (iii) of the previous claim implies that no block has four cutpoints such that two of them labeled B, and item (iv) of the previous claim implies that no block has three cutpoints labeled B.

Since, by item (i), no block has five or more cutpoints, the possible label multisets for the blocks of G are $\{A\}$, $\{B\}$, $\{A,A\}$, $\{A,B\}$, $\{B,B\}$, $\{A,A,A\}$, $\{A,A,B\}$, $\{A,B,B\}$, $\{A,A,A,A\}$ and $\{A,A,A,B\}$.

Let $i=1$, so $G_i$ has only one block $H_1$. Note that $H_1$ is $H^c$ for every cutpoint c of G belonging to $H_1$. So, considering the label multiset of the vertices of $H_1$, the cases $\{A,A,A,B\}$ and $\{A,B,B\}$ cannot arise (by items (iii) and (iv) of the claim, respectively). In the cases $\{A\}$, $\{B\}$, and $\{A,A\}$, the block can be represented either as a line clique or as a cross clique, satisfying the conditions. In the cases $\{A,B\}$ and $\{B,B\}$, the block can be represented as a cross clique where one of the labeled vertices is the farthest North and South line, and the other one is the farthest East and West line. In the cases $\{A,A,A\}$ and $\{A,A,B\}$, the block can be represented as a cross clique where one of the labeled vertices (the vertex labeled B in the second case) is the farthest North and South line, and the other two are the farthest East, respectively West, line. In the case $\{A,A,A,A\}$, the block can be represented as a cross clique where each labeled vertex corresponds to the farthest North, South, East or West line.

We will proceed now by induction. Let $i > 1$, and let $v:=c(i)$, the only cutpoint of $H_i$ appearing in s before $H_i$. Let $H_j, H_{j+1}, \ldots , H_i$ be the blocks between v and $H_i$ containing v (it can be $j=i$). As noticed above, $H_j, H_{j+1}, \ldots , H_i$ are endblocks, and since the first element of s is a block, $j > 1$. In particular, $H^{v} \subseteq G_{j-1}$. Notice also that for $j \le k \le i$ and for every cutpoint c of G, different from v, that belongs to $H_k$, it holds $H_k = H^c$.

We know by the inductive hypothesis that there is a $B_0$-VPG representation of $G_{j-1}$ such that each cutpoint c of G that belongs to $G_{j-1}$ corresponds to the farthest North, South, East or West line of the line or cross representation of the clique $H^c$ and, moreover, if c is labeled B, then it corresponds to the farthest North and South, or East and West (simultaneously) line of the line or cross representation of the clique $H^c$.

We will show that, possibly refining the grid, we can extend this representation to a representation of $G_i$ with the desired properties.

We will consider the possible cases for the label of v and the remaining labeled vertices of $H_j, \ldots , H_i$.

Case 1  v is labeled B.

Without loss of generality, assume that vertex v corresponds to the farthest North and South line of the representation of $H^v$, say $P_v$. As $H^v$ is the only clique of $G_{j-1}$ containing v, $P_v$ has two segments $P_v^N$ and $P_v^S$ that do not intersect any other path in $G_{j-1}$, and each of them contains an endpoint of $P_v$.

Since v is labeled B, we have that the possible multisets for the blocks $H_j, \ldots , H_i$ are $\{B\}$, $\{A,B\}$, $\{B,B\}$, $\{A,A,B\}$, $\{A,B,B\}$, and $\{A,A,A,B\}$. By the item (ii) of the claim, at most two of them have labels $\{A,A,A,B\}$ or $\{A,B,B\}$ (there are exactly two such blocks in G, but some of them may have index greater than i). We will assign to each block a segment of $P_v^N$ or $P_v^S$, in such a way that the blocks having labels $\{A,A,A,B\}$ or $\{A,B,B\}$ receive the segments of $P_v^N$, respectively $P_v^S$, that contain an endpoint of $P_v$. It is easy to see that we can extend the representation to a $B_0$-VPG representation of H satisfying the required properties:

• in the case of labels $\{B\}$, we add the remaining vertices in a line clique on the assigned segment;

• in the case of labels $\{A,B\}$ or $\{B,B\}$, we add the remaining vertices in a cross clique on the assigned segment, in such a way that the other labeled vertex corresponds to the farthest East and West line of the clique;

• in the case of labels $\{A,A,B\}$, we add the remaining vertices in a cross clique on the assigned segment, in such a way that the other two labeled vertices correspond to the farthest East, respectively West, line of the clique;

• in the case of labels $\{A,B,B\}$, we add the remaining vertices in a cross clique on the assigned segment, in such a way that the other vertex labeled B corresponds to the farthest East and West line of the clique, and the third labeled vertex corresponds to the farthest North line if the segment assigned contains the North endpoint of $P_v$, and to the farthest South line, otherwise;

• finally, in the case of labels $\{A,A,A,B\}$, we add the remaining vertices in a cross clique on the assigned segment, in such a way that two of the other labeled vertices correspond to the farthest East, respectively West, line of the clique, and the third labeled vertex corresponds to the farthest North line if the segment assigned contains the North endpoint of $P_v$, and to the farthest South line, otherwise.

For a scheme, see Fig. 4a.

Fig. 4

Scheme for the extension of a representation of $G_{j-1}$ to $G_{i}$. The cutpoints are represented by bold lines

Case 2  v is labeled A.

Without loss of generality, assume that vertex v corresponds to the farthest North line of the representation of $H^v$, say $P_v$. As $H^v$ is the only clique of $G_{j-1}$ containing v, $P_v$ has a segment $P_v^N$ that does not intersect any other path, and contains the North endpoint of $P_v$.

Since v is labeled A, the possible multisets for the blocks $H_j, \ldots , H_i$ are $\{A\}$, $\{A,A\}$, $\{A,B\}$, $\{A,A,A\}$, $\{A,A,B\}$, $\{A,A,A,A\}$. Notice that, since for $j \le k \le i$ and for every cutpoint c of G, different from v, that belongs to $H_k$, it holds $H_k = H^c$, the multisets $\{A,A,A,B\}$ and $\{A,B,B\}$ cannot arise (by items (iii) and (iv) of the claim, respectively).

By the labeling rules, at most one block in $H_j, \ldots , H_i$ has labels $\{A,A,A,A\}$ or $\{A,A,B\}$. We will assign to each block a segment of $P_v^N$, in such a way that the block having labels $\{A,A,A,A\}$ or $\{A,A,B\}$ receives the segment of $P_v^N$ that contains the North endpoint of $P_v$. It is easy to see that we can extend the representation to a $B_0$-VPG representation of H satisfying the required properties:

• in the case of labels $\{A\}$, we add the remaining vertices in a line clique on the assigned segment;

• in the case of labels $\{A,A\}$ or $\{A,B\}$, we add the remaining vertices in a cross clique on the assigned segment, in such a way that the other labeled vertex corresponds to the farthest East and West line of the clique;

• in the case of labels $\{A,A,A\}$, we add the remaining vertices in a cross clique on the assigned segment, in such a way that the other two labeled vertices correspond to the farthest East, respectively West, line of the clique;

• in the case of labels $\{A,A,B\}$, we add the remaining vertices in a cross clique on the assigned segment, in such a way that the vertex labeled B corresponds to the farthest East and West line of the clique, and the third labeled vertex corresponds to the farthest North line of the clique;

• finally, in the case of labels $\{A,A,A,B\}$, we add the remaining vertices in a cross clique on the assigned segment, in such a way that two of the other labeled vertices correspond to the farthest East, respectively West, line of the clique, and the third labeled vertex corresponds to the farthest North line of the clique.

For a scheme, see Fig. 4b.

The minimality holds by the equivalence of $B_0$-VPG and ${\mathcal {F}}$-free within block graphs, and Corollary 4. $\square$

Corollary 10

Let G be a chordal diamond-free VPG graph. Then G is a $B_0$-VPG graph if and only if G is ${\mathcal {F}}$-free.

Proof

It follows directly by the fact that block graphs are connected chordal diamond-free graphs. $\square$

4 Conclusion

In this paper we consider $B_0$-VPG graphs, that is, intersection graphs of paths on a grid such that each path is either a horizontal path or a vertical path on the grid. We characterize whether a block graph is a $B_0$-VPG graph in terms of minimal forbidden induced subgraphs.

The proof of Theorem 9 (i.e., the labeling process and the conditions of the claim) provides an alternative recognition and representation algorithm for $B_0$-VPG graphs in the class of block graphs. This algorithm is a certifying algorithm, since if the answer is negative it provides a minimal forbidden induced subgraph.