1 Introduction

The square of a graph H, denoted \(H^2\), is obtained from H by adding new edges between two distinct vertices whenever their distance is two. Then, H is called a square root of \(G=H^2\). Given a graph G, it is NP-complete to decide if G is the square of some graph H [23], even for a split graph H [16].

Given a bipartite graph \(B=(X,Y,E_B)\), the subgraphs of the square \(B^2\) induced by the color classes X and Y, \(B^2[X]\) and \(B^2[Y]\), are called the two half-squares of B [4].

While not every graph is the square of a graph and deciding if a graph is the square of a graph is hard, every graph \(G=(V,E_G)\) is half-square of a bipartite graph: if \(B=(V,E_G,E_B)\) is the bipartite graph with \(E_B=\{ve \mid v\in V, e\in E_G, v\in e\}\), then clearly \(G=B^2 [V]\). So one is interested in half-squares of special bipartite graphs. Note that B is the subdivision of G, hence every planar graph is half-square of a planar bipartite graph.

Let \(\mathcal B\) be a class of bipartite graphs. A graph \(G=(V,E_G)\) is called half-square of \(\mathcal B\) if there exists a bipartite graph \(B=(V,W,E_B)\) in \(\mathcal B\) such that \(G=B^2[V]\). Then, B is called a \(\mathcal{B}\) -half root of G. With this notion, the following decision problem arises.

figure a

In this paper, we discuss Half-Square Of \(\mathcal B\)  for several restricted bipartite graph classes \(\mathcal B\).

Previous results and related work.  Half-squares of bipartite graphs have been introduced in [4] in order to give a graph-theoretical characterization of the so-called map graphs. It turns out that map graphs are exactly half-squares of planar bipartite graphs. As we have seen at the beginning, every planar graph is a map graph. The main problem concerning map graphs is to recognize if a given graph is a map graph. In [27], Thorup shows that Half-Square Of Planar, that is, deciding if a graph is a half-square of a planar bipartite graph, can be solved in polynomial timeFootnote 1. Very recently, in [22], it is shown that Half-Squares Of Outerplanar and Half-Square Of Tree are solvable in linear time. Other papers deal with solving hard problems in map graphs include [3, 5, 6, 8]. Some applications of map graphs have been addressed in [1].

Our results.  We identify the first class \(\mathcal B\) of bipartite graphs for which Half-Square Of \(\mathcal B\)  is NP-hard. Our class \(\mathcal B\) is a subclass of the class of the bisplit bipartite graphs and of star convex bipartite graphs (all terms are given later). For some other subclasses of bipartite graphs, such as biconvex, convex, and chordal bipartite graphs, we give structural descriptions for their half-squares, that imply polynomial-time recognition algorithms:

  • Recognizing half-squares of balanced bisplit graphs (a proper subclass of star convex bipartite graphs) is hard, even when restricted to co-bipartite graphs;

  • Half-squares of biconvex bipartite graphs are precisely the unit interval graphs;

  • Half-squares of convex bipartite graphs are precisely the interval graphs;

  • Half-squares of chordal bipartite graphs are precisely the strongly chordal graphs.

2 Preliminaries

Let \(G=(V,E_G)\) be a graph with vertex set \(V(G)=V\) and edge set \(E(G)=E_G\). A stable set (a clique) in G is a set of pairwise non-adjacent (adjacent) vertices. The complete graph on n vertices, the complete bipartite graph with s vertices in one color class and t vertices in the other color class, the cycle with n vertices are denoted \(K_n, K_{s,t}\), and \(C_n\), respectively. A \(K_3\) is also called a triangle, a complete bipartite graph is also called a biclique, a complete bipartite graph \(K_{1,n}\) is also called a star.

The neighborhood of a vertex v in G, denoted by \(N_G(v)\), is the set of all vertices in G adjacent to v; if the context is clear, we simply write N(v). A universal vertex v in G is one with \(N(v)=V\setminus \{v\}\), i.e., v is adjacent to all other vertices in G.

For a subset \(W\subseteq V\), G[W] is the subgraph of G induced by W, and \(G-W\) stands for \(G[V\setminus W]\). We write \(B=(X,Y,E_B)\) for bipartite graphs with a bipartition into stable sets X and Y. For subsets \(S\subseteq X\), \(T\subseteq Y\) we denote B[S, T] for the bipartite subgraph of B induced by \(S\cup T\).

We will consider half-squares of the following well-known subclasses of bipartite graphs: Let \(B=(X,Y,E_B)\) be a bipartite graph.

  • B is X-convex if there is a linear ordering on X such that, for each \(y\in Y\), N(y) is an interval in X. Being Y-convex is defined similarly. B is convex if it is X-convex or Y-convex. B is biconvex if it is both X-convex and Y-convex. We write Convex and Biconvex to denote the class of convex bipartite graphs, respectively, the class of biconvex bipartite graphs.

  • B is chordal bipartite if B has no induced cycle of length at least six.

    Chordal Bipartite stands for the class of chordal bipartite graphs.

  • B is tree X-convex if there exists a tree \(T=(X,E_T)\) such that, for each \(y\in Y\), N(y) induces a subtree in T. Being tree Y-convex is defined similarly. B is tree convex if it is tree X-convex or tree Y-convex. B is tree biconvex if it is both tree X-convex and tree Y-convex. When T is a star, we also speak of star convex and star biconvex bipartite graphs.

    Tree Convex and Tree Biconvex are the class of all tree convex and all tree biconvex bipartite graphs, respectively, and Star Convex and Star Biconvex are the class of all star convex and all star biconvex bipartite, respectively.

It is known that Biconvex \(\subset \) Convex \(\subset \) Chordal Bipartite \(\subset \) Tree Biconvex \(\subset \) Tree Convex. All inclusions are proper; see [2, 19, 26] for more information on these graph classes.

Given a graph G, we often use the following two kinds of bipartite graphs associated to G:

Definition 1

Let \(G=(V,E_G)\) be an arbitrary graph.

  • The bipartite graph \(B=(V,E_G, E_B)\) with \(E_B=\{ve\mid v\in V, e\in E_G, v\in e\}\) is the subdivision of G.

  • Let \(\mathcal{C}(G)\) denote the set of all maximal cliques of G. The bipartite graph \(B=(V,\mathcal{C}(G),E_B)\) with \(E_B=\{vQ\mid v\in V, Q\in \mathcal{C}(G), v\in Q\}\) is the vertex-clique incidence bipartite graph of G.

Note that the subdivision of a planar graph is planar, and subdivisions and vertex-clique incidence graphs of triangle-free graphs coincide.

Proposition 1

Every graph is half-square of its vertex-clique incidence bipartite graph. More precisely, if \(B=(V,\mathcal{C}(G), E_B)\) is the vertex-clique incidence bipartite graph of \(G=(V,E_G)\), then \(G=B^2[V]\). Similar statement holds for subdivisions.

Proof

For distinct vertices \(u, v\in V\), \(uv\in E_G\) if and only if \(u, v\in Q\) for some \(Q\in \mathcal{C}(G)\), if and only if u and v are adjacent in \(B^2[V]\). That is, \(G=B^2[V]\).    \(\square \)

3 Recognizing Half-Squares of Balanced Bisplit Graphs Is Hard

Recall that a biclique is a complete bipartite graph. Following the concept of split graphs, we call a bipartite graph bisplit if it can be partitioned into a biclique and a stable set. In this section, we show that Half-Square Of Balanced Bisplit is NP-hard. Balanced bisplit graphs form a proper subclass of bisplit graphs, and are defined as follows.

Definition 2

A bipartite graph \(B=(X,Y,E_B)\) is called balanced bisplit if it satisfies the following properties:

  • (i) \(|X| = |Y|\);

  • (ii) there is partition \(X=X_1\,\dot{\cup }\, X_2\) such that \(B[X_1,Y]\) is a biclique;

  • (iii) there is partition \(Y=Y_1\,\dot{\cup }\, Y_2\) such that the edge set of \(B[X_2,Y_2]\) is a perfect matching.

Note that by (i) and (iii), \(|X_1|=|Y_1|\), and by (ii) and (iii), every vertex in \(X_1\) is universal in \(B^2[X]\).

In order to prove the NP-hardness of Half-Square Of Balanced Bisplit, we will reduce the following well-known NP-complete problem Edge Clique Cover to it.

figure b

Edge Clique Cover is NP-complete [12, 14, 24], even when restricted to co-bipartite graphs [17]. (A co-bipartite graph is the complement of a bipartite graph.)

Theorem 1

Half-Square Of Balanced Bisplit is NP-complete, even when restricted to co-bipartite graphs.

Proof

It is clear that Half-Square Of Balanced Bisplit is in NP, since guessing a bipartite-half root \(B=(V,W,E_B)\) with \(|W|=|V|\), verifying that B is balanced bisplit, and \(G = B^2[V]\) can obviously be done in polynomial time. Thus, by reducing Edge Clique Cover to Half-Square Of Balanced Bisplit, we will conclude that Half-Square Of Balanced Bisplit is NP-complete.

Let \((G=(V,E_G),k)\) be an instance of Edge Clique Cover. Note that we may assume that \(k\le |E_G|\), and that G is connected and has no universal vertices. We construct an instance \(G'=(V',E_{G'})\) as follows: \(G'\) is obtained from G by adding a set U of k new vertices, \(U=\{u_1,\ldots , u_k\}\), and all edges between vertices in U and all edges uv with \(u\in U\), \(v\in V\). Thus, \(V'=V\cup U\), \(G'[V]=G\) and the k new vertices in U are exactly the universal vertices of \(G'\). Clearly, \(G'\) can be constructed in polynomial time \(O(k|V|)=O(|E_G|\cdot |V|)\), and in addition, if G is co-bipartite, then \(G'\) is co-bipartite, too. We now show that \((G,k)\in \) Edge Clique Cover if and only if \(G'\in \) Half-Square Of Balanced Bisplit.

First, suppose that the edges of \(G=(V,E_G)\) can be covered by k cliques \(Q_1,\ldots , Q_k\) in G. We are going to show that \(G'\) is half-square of some balanced bisplit bipartite graph. Consider the bipartite graph \(B=(V',W,E_B)\) (see also Fig. 1) with

$$\begin{aligned} W=W_1\cup W_2,\, \text { where }\, W_1=\{w_1, \ldots , w_k\},\,\text { and }\, W_2=\{w_v\mid v\in V\}. \end{aligned}$$

In particular, \(|V'|=|W|=k+|V|\). The edge set \(E_B\) is as follows:

  • B has all edges between U and W, i.e., B[U, W] is a biclique,

  • B has edges \(vw_v\), \(v\in V\). Thus, the edge set of \(B[V,W_2]\) forms a perfect matching, and

  • B has edges \(vw_i\), \(v\in V\), \(1\le i\le k\), whenever \(v\in V\) is contained in clique \(Q_i\), \(1\le i\le k\).

Fig. 1.
figure 1

The balanced bisplit graph \(B=(V',W,E_B)\) proving \(G'=B^2[V']\); \(v\in V\) is adjacent to \(w_i\in W_1\) if and only if \(v\in Q_i\).

Full size image

Thus, B is a balanced bisplit graph. Moreover, by the construction of B, we have in \(B^2[V']\):

  • \(U=\{u_1,\ldots ,u_k\}\) is a clique (as B[U, W] is a biclique);

  • every vertex \(u\in U\) is adjacent to all vertices \(v\in V\) (recall that G is connected, so every \(v\in V\) is in some \(Q_i\), and \(w_i\in W_1\) is a common neighbor of u and v), and

  • no two distinct vertices \(v, z\in V\) have common neighbor in \(W_2\). So u and z are adjacent in \(B^2[V']\) if and only if v and z have a common neighbor \(w_i\) in \(W_1\), if and only if v and z belong to clique \(Q_i\) in G, if and only if u and z are adjacent in G.

That is, \(G'=B^2[V']\).

Conversely, suppose \(G'=H^2[V']\) for some balanced bisplit graph \(H=(V',Y,E_H)\) with \(|V'|=|Y|\) and partitions \(V'=X_1\,\dot{\cup }\,X_2\) and \(Y=Y_1\,\dot{\cup }\, Y_2\) as in Definition 2. We are going to show that the edges of G can be covered by k cliques. As \(H[X_1,Y]\) is a biclique, all vertices in \(X_1\) are universal in \(H^2[V']=G'\). Hence

$$\begin{aligned} X_1=U \end{aligned}$$

because no vertex in \(V=V'\setminus U\) is universal in \(G'\) (recall that G has no universal vertex). Therefore

$$\begin{aligned} X_2=V \text { and } G=H^2[V]. \end{aligned}$$

Note that, as H is a balanced bisplit graph, \(|Y_1|=|U|=k\). Write \(Y_1=\{q_1,\ldots , q_k\}\) and observe that no two vertices in V have a common neighbor in \(Y_2\). Thus, for each edge vz in \(G=H^2[V]\), v and z have a common neighbor \(q_i\) in \(Y_1\). Therefore, the k cliques \(Q_i\) in \(H^2[V]\), \(1\le i\le k\), induced by the neighbors of \(q_i\) in V, cover the edges of G.    \(\square \)

Theorem 1 indicates that recognizing half-squares of restricted bipartite graphs is algorithmically much more complex than recognizing squares of bipartite graphs; the latter can be done in polynomial time [15].

Observe that balanced bisplit graphs are star convex: Let \(B=(X,Y,E_B)\) be a bipartite graph with the properties in Definition 2. Fix a vertex \(u\in X_1\) and consider the star \(T=(X,\{uv\mid v\in X-u\})\). Since every vertex \(y\in Y\) is adjacent to u, N(y) induces a substar in T. Note, however, that the hardness of Half-Square Of Balanced Bisplit does not imply the hardness of Half-Square Of Star Convex. This is because the proof of Theorem 1 strongly relies on the properties of balanced bisplit graphs. Indeed, in the meantime, we are able to show that half-squares of star-convex bipartite graphs can be recognized in polynomial time. This result will be included in the full version of this conference paper.

4 Half-Squares of Biconvex and Convex Bipartite Graphs

In this section, we show that half-squares of convex bipartite graphs are precisely the interval graphs and half-squares of biconvex bipartite graphs are precisely the unit interval graphs.

Recall that \(G=(V,E_G)\) is an interval graph if it admits an interval representation \(I(v), v\in V\), such that two vertices in G are adjacent if and only if the corresponding intervals intersect. Let G be an interval graph. It is well-known [9, 10] that there is a linear ordering of the maximal cliques of G, say \(\mathcal{C}(G)=(Q_1,\ldots ,Q_q)\), such that every vertex of G belongs to maximal cliques that are consecutive in that ordering, that is, for every vertex u of G, there are indices \(\ell (u)\) and r(u) with

$$\begin{aligned} \{ i\mid 1\le i\le q \text{ and } u\in Q_i\}=\{ i\mid \ell (u)\le i\le r(u)\}. \end{aligned}$$

If C and D are distinct maximal cliques of G, then \(C\setminus D\) and \(D\setminus C\) are both not empty, that is, for every \(j\in \{ 1,\ldots ,q\}\), there are vertices u and v such that \(r(u)=\ell (v)=j\).

Recall that unit interval graphs are those interval graphs admitting an interval representation in which all intervals have the same length. It is well known [25] that a graph is a unit interval graphs if and only if it has an interval representation in which no interval is properly contained in another interval (a proper interval graph), if and only if it is a \(K_{1,3}\)-free interval graph.

Lemma 1

The half-squares of a biconvex bipartite graph are \(K_{1,3}\)-free.

Proof

Let \(B=(X,Y,E_B)\) be a biconvex bipartite graph. By symmetry we need only to show that \(B^2[X]\) is \(K_{1,3}\)-free. Suppose, by contradiction, that \(x_1, x_2, x_3, x_4\) induce a \(K_{1,3}\) in \(B^2[X]\) with edges \(x_1x_2, x_1x_3\) and \(x_1x_4\). Let \(y_i\) be a common neighbor of \(x_1\) and \(x_2\), \(y_j\) be a common neighbor of \(x_1\) and \(x_3\), and \(y_k\) be a common neighbor of \(x_1\) and \(x_4\). Then, \(y_i, y_j, y_k\) are pairwise distinct and induce, in B, a subdivision of \(K_{1,3}\). This is a contradiction because biconvex bipartite graphs do not contain an induced subdivision of the \(K_{1,3}\). Thus, the half-squares of a biconvex bipartite graph are \(K_{1,3}\)-free.    \(\square \)

Lemma 2

  • (i) Every interval graph is half-square of a convex bipartite graph. More precisely, if \(G=(V,E_G)\) is an interval graph and \(B=(V,\mathcal{C}(G), E_B)\) is the vertex-clique incidence bipartite graph of G, then \(G=B^2[V]\) and B is \(\mathcal{C}(G)\)-convex.

  • (ii) If \(B=(X,Y,E_B)\) is X-convex, then \(B^2[Y]\) is an interval graph.

Proof

(i) Let \(G=(V,E_G)\) be an interval graph, and let \(B=(V,\mathcal{C}(G),E_B)\) be the vertex-clique incidence bipartite graph of G. Since each \(v\in V\) appears in the interval \(\{Q_i\mid \ell (v)\le i\le r(v)\}\) in \(\mathcal{C}(G)=(Q_1,\ldots , Q_q)\), B is \(\mathcal{C}(G)\)-convex. Moreover, by Proposition 1, \(G=B^2[V]\).

(ii) This is because X admits a linear ordering such that, for each \(y\in Y\), N(y) is an interval in X. This collection is an interval representation of \(B^2[Y]\) because y and \(y'\) are adjacent in \(B^2[Y]\) if and only if \(N(y)\cap N(y')\not =\emptyset \).    \(\square \)

Theorem 2

A graph is half-square of a biconvex bipartite graph if and only if it is a unit interval graph.

Proof

First, by Lemma 2 (ii), half-squares of biconvex bipartite graphs are interval graphs, and then by Lemma 1, half-squares of biconvex bipartite graphs are unit interval graphs.

Next we show that every unit interval graph is half-square of some biconvex bipartite graph. Let \(G=(V,E_G)\) be a unit interval graph. Let \(B=(V, \mathcal{C}(G), E_B)\) be the vertex-clique incidence bipartite graph of G. By Lemma 2 (i), \(G=B^2[V]\) and B is \(\mathcal{C}(G)\)-convex. We now are going to show that B is V-convex, too.

Consider a linear order in \(\mathcal{C}(G)\), \(\mathcal{C}(G)=(Q_1,\ldots , Q_q)\), such that each \(v\in V\) is contained in exactly the cliques \(Q_i\), \(\ell (v)\le i\le r(v)\). Let \(v\in V\) be lexicographically sorted according \((\ell (v),r(v))\). We claim that B is V-convex with respect to this ordering. Assume, by a contradiction, that some \(Q_i\) has neighbors v, u and non-neighbor x with \(v< x < u\) in the sorted list, say. In particular, v, u belong to \(Q_i\), but x not; see also Fig. 2.

Fig. 2.
figure 2

Assuming \(v<x<u\), and \(v,u\in Q_i\), but \(x\not \in Q_i\).

Full size image

Since \(x < u\) and \(\ell (u)\le i\), we have \(\ell (x) <i\). Since u is not in \(Q_i\), we therefore have

$$\begin{aligned} \ell (x)\le r(x) < i. \end{aligned}$$

In particular, \(r(x)+1\le i\). Since \(v < x\) and \(r(v) \ge i\), we have

$$\begin{aligned} \ell (v) < \ell (x). \end{aligned}$$

In particular, \(\ell (x)-1 \ge 1\). Now, by the maximality of the cliques, there exists \(y\in Q_{\ell (x)-1}\) with \(r(y)=\ell (x)-1\) (hence y is non-adjacent to x), and there exists \(z\in Q_{r(x)+1}\) with \(\ell (z)=r(x)+1\) (hence z is non-adjacent to x and y; note that \(r(x)+1=i\) and \(z=u\) are possible). But then v, x, y, and z induce a \(K_{1,3}\) in G, a contradiction.

Thus, we have seen that every unit interval graph is half-square of a biconvex bipartite graph.    \(\square \)

We next characterize half-squares of convex bipartite graphs as interval graphs. This is somehow surprising because the definition of being convex bipartite is asymmetric with respect to the two half-squares.

Theorem 3

A graph is a half-square of a convex bipartite graph if and only if it is an interval graph.

Proof

By Lemma 2 (i), interval graphs are half-squares of convex bipartite graphs. It remains to show that half-squares of convex bipartite graphs are interval graphs. Let \(B=(X,Y,E_B)\) be an X-convex bipartite graph. By Lemma 2 (ii), \(B^2[Y]\) is an interval graph. We now are going to show that \(B^2[X]\) is an interval graph, too.

Let \(B'=(X,Y',E_{B'})\) be obtained from B by removing all vertices \(y\in Y\) such that \(N_B(y)\) is properly contained in \(N_B(y')\) for some \(y'\in Y\). Clearly, \(B^2[X]=B'^2[X]\). We show that \(B'\) is \(Y'\)-convex, hence, by Lemma 2 (ii), \(B^2[X]=B'^2[X]\) is an interval graph, as claimed. To this end, let \(X=\{x_1,\ldots , x_n\}\) such that, for every \(y\in Y'\), \(N_{B'}(y)\) is an interval in X. (Recall that B, hence \(B'\) is X-convex.) For \(y\in Y'\) let \(\text {left}(y)=\min \{i\mid x_i\in N_{B'}(y)\}\), and sort \(y\in Y'\) increasing according \(\text {left}(y)\). Then, for each \(x\in X\), \(N_{B'}(x)\) is an interval in \(Y'\): Assume, by contradiction, that there is some \(x\in X\) such that \(N_{B'}(x)\) is not an interval in \(Y'\). Let y be a leftmost and \(y'\) be a rightmost vertex in \(N_{B'}(x)\). By the assumption, there is some \(y''\in Y'\setminus N_{B'}(x)\) with \(\text {left}(y)< \text {left}(y'') < \text {left}(y')\). Then, as \(N_{B'}(y), N_{B'}(y'')\) and \(N_{B'}(y')\) are intervals in X, \(N_{B'}(y'')\) must be a subset of \(N_{B'}(y)\); see also Fig. 3. Since \(x\in N_{B'}(y)\) but \(x\not \in N_{B'}(y'')\), \(N_{B'}(y'')\) must be a proper subset of \(N_{B'}(y)\), contradicting to the fact that in \(B'\), no such pair of vertices exists in \(Y'\). Thus, \(B'\) is \(Y'\)-convex.

Fig. 3.
figure 3

Assuming \(\text {left}(y)<\text {left}(y'')< \text {left}(y')\), and x is adjacent to y and \(y'\), but non-adjacent to \(y''\).

Full size image

Note that \(B'\) is indeed biconvex, hence, by Theorem 2, \(B^2[X]=B'^2[X]\) is even a unit interval graph.    \(\square \)

Since (unit) interval graph with n vertices and m edges can be recognized in linear time \(O(n+m)\) and all maximal cliques of an (unit) interval graph can be listed in the same time complexity (cf. [11]), Theorems 3 and 2 imply:

Corollary 1

Half-Square Of Convex and Half-Square Of Biconvex can be solved in linear time. A (bi)convex bipartite half-root, if any, can be constructed in linear time.

5 Half-Squares of Chordal Bipartite Graphs

In this section, we show that half-squares of chordal bipartite graphs are precisely the strongly chordal graphs. Recall that a graph is chordal if it has no induced cycle of length at least four. It is well-known (see, e.g., [11, 21, 26]) that a graph \(G=(V,E_G)\) is chordal if and only if it admits a tree representation, that is, there exists a tree T such that, for each vertex \(v\in V\), \(T_v\) is a subtree of T and two vertices in G are adjacent if and only if the corresponding subtrees in T intersect. Moreover, the vertices of T can be taken as the maximal cliques of the chordal graph (a clique tree). Recall also that a graph is strongly chordal if it is chordal and has no induced k-sun, \(k\ge 3\). Here a k-sun consists of a stable set \(\{s_1,\ldots , s_k\}\) and a clique \(\{t_1,\ldots ,t_k\}\) and edges \(s_it_i\), \(s_it_{i+1}\), \(1\le i\le k\). (Indices are taken modulo k.)

We first begin with the following fact.

Lemma 3

Let \(B=(V,W,E_B)\) be bipartite graph without induced \(C_6\) and let \(k\ge 3\). If \(B^2[V]\) contains an induced k-sun, then B contains an induced cycle of length 2k.

The proof of Lemma 3 will be given in the full version of this paper.

Theorem 4

A graph is half-square of a chordal bipartite graph if and only if it is a strongly chordal graph.

Proof

We first show that half-squares of chordal bipartite graphs are chordal. Let \(B=(X,Y,E_B)\) be a chordal bipartite graph. It is known that B is tree convex [13, 18]. Thus, there is a tree \(T=(X,E_T)\) such that, for each \(y\in Y\), N(y) induces a subtree in T. Then, for distinct vertices \(y, y'\in Y\), y and \(y'\) are adjacent in \(B^2[Y]\) if and only if \(N(y)\cap N(y')\not =\emptyset \), and thus, \(B^2[Y]\) has a tree representation, hence chordal. Now, by Lemma 3, \(B^2[Y]\) cannot contain any sun k-sun, \(k\ge 3\), showing that it is a strongly chordal graph. By symmetry, \(B^2[X]\) is also strongly chordal. We have seen that half-squares of chordal bipartite graphs are strongly chordal graphs.

Next, let \(G=(V,E_G)\) be a strongly chordal graph, and let \(B=(V,\mathcal{C}(G), E_B)\) be the vertex-clique incidence bipartite graph of G. By Proposition 1, \(G=B^2[V]\). Moreover, it is well-known [7] that B is chordal bipartite. Thus, every strongly chordal graph is a half-square of some chordal bipartite graph, namely of its vertex-clique incidence bipartite graph.    \(\square \)

Testing if G is strongly chordal can be done in \(O(\min \{n^2,m\log n\})\) time [7, 20, 26]. Assuming G is strongly chordal, all maximal cliques \(Q_1\), ..., \(Q_q\) of G can be listed in linear time (cf. [11, 26]); note that \(q\le n\). So, Theorem 4 implies:

Corollary 2

Half-Square Of Chordal Bipartite can be solved in time \(O(\min \{n^2,m\log n\})\), where n and m are the vertex and edge number of the input graph, respectively. A chordal bipartite half-root, if any, can be constructed in the same time complexity.

Theorem 4 (and its proof) gives another proof for a characterization of half-squares of trees found in [22]. A block graph is one in which every maximal 2-connected subgraph (a block) is a complete graph; equivalently, a block graph is a chordal graph without induced \(K_4-e\), a \(K_4\) minus an edge.

Theorem 5

([22]). Half-squares of trees are exactly the block graphs.

6 Conclusions

Until recently, only half-squares of planar bipartite graphs (the map graphs) have been investigated, and the most considered problem is if it is possible to recognize these graphs faster and simpler than Thorup’s \(O(n^{120})\) time algorithm.

In this paper, we have shown the first NP-hardness result, namely that recognizing if a graph is half-square of a balanced bisplit graph is NP-complete. For classical subclasses of tree convex bipartite graphs such as biconvex, convex, and chordal bipartite graphs, we have given good structure characterizations for their half-squares. These structural results imply that half-squares of these restricted classes of bipartite graphs can be recognized efficiently.

Recall that chordal bipartite graphs form a subclass of tree biconvex bipartite graphs [13, 18], and that half-squares of chordal bipartite graphs can be recognized in polynomial time, while the complexity of recognizing half-squares of tree (bi)convex bipartite graphs is unknown. So, an obvious question is: what is the computational complexity of Half-Square Of Tree (Bi)convex?