Biró, Hujter, and Tuza (1992) introduced the concept of $H$-graphs, intersection graphs of connected subregions of a graph $H$ thought of as a one-dimensional simplicial complex. They relate to and generalize many important classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs.

Surprisingly, we negatively answer the 25-year-old question of Biró, Hujter, and Tuza which asks whether $H$-graphs can be recognized in polynomial time, for a fixed graph $H$. Moreover, our paper opens a new research area in the field of geometric intersection graphs by studying $H$-graphs from the point of view of fundamental computational problems of theoretical computer science: recognition, graph isomorphism, dominating set, clique, and colourability.

For the recognition problem, we prove that it is $NP$-complete if $H$ contains the diamond as a minor. For each fixed tree $T$, we provide a polynomial-time algorithm recognizing $T$-graphs. When $T$ is a star $S_d$ of degree $d$, the running time improves to $O(n^4)$.

For the minimum dominating set problem, we give $FPT$- and $XP$-time algorithms solving the problem on $S_d$-graphs (paramterized by $d$) and $H$-graphs (parameterized by the size of $H$), respectively. As a byproduct, the dominating set algorithm for $H$-graphs also provides $XP$-time algorithm for the independent set and the independent dominating set problems on $H$-graphs.

If $H$ contains the double triangle as a minor, we prove that the graph isomorphism problem is $GI$-complete and that the clique problem is $APX$-hard. On the positive side, we show that the clique problem can be solved in polynomial time if $H$ is a cactus. Also, when a graph $G$ has a Helly $H$-representation, the clique problem can be solved in polynomial time.

Finally, we use treewidth techniques to show that both the $k$-clique and the list $k$-coloring problems are solvable in $FPT$-time (parameterized by $k$ and the treewidth of $H$) on $H$-graphs.