Department of
Applied
Mathematics

On H-topological intersection graphs

Peter Zeman

Abstract

(joint work with: Steven Chaplick, Martin Töpfer, Jan Voborník)

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 topological space. 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 graph 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, we have a recognition algorithm with running time 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.