  Let $B=(X,Y,E)$ be a bipartite graph. A half-square of $B$ has one color
class of $B$ as vertex set, say $X$; two vertices are adjacent whenever they
have a common neighbor in $Y$. Every planar graph is a half-square of a planar
bipartite graph, namely of its subdivision. Until recently, only half-squares
of planar bipartite graphs, also known as map graphs (Chen, Grigni and
Papadimitriou [STOC 1998, J. ACM 2002]), have been investigated, and the most
discussed problem is whether it is possible to recognize these graphs faster
and simpler than Thorup's $O(n^{120})$-time algorithm (Thorup [FOCS 1998]).
  In this paper, we identify the first hardness case, namely that deciding if a
graph is a half-square of a balanced bisplit graph is NP-complete. (Balanced
bisplit graphs form a proper subclass of star convex bipartite graphs.) For
classical subclasses of tree convex bipartite graphs such as biconvex, convex,
and chordal bipartite graphs, we give good structural characterizations of
their half-squares that imply efficient recognition algorithms. As a
by-product, we obtain new characterizations of unit interval graphs, interval
graphs, and of strongly chordal graphs in terms of half-squares of biconvex
bipartite, convex bipartite, and of chordal bipartite graphs, respectively.
Good characterizations of half-squares of star convex and star biconvex
bipartite graphs are also given, giving linear-time recognition algorithms for
these half-squares.
