2019/07/02 by Deniz Ağaoğlu Çağırıcı, Çağırıcı, Deniz Ağaoğlu, Petr Hliněný +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1907.01495
openalex publication_date 2019/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró, Hujter and Tuza (1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for Sd-graphs and T-graphs, where Sd is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick, Töpfer, Voborn'ık and Zeman (2016), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of Sd-graphs when parameterized by~d, which involves the classical group-computing machinery by Furst, Hopcroft, and Luks (1980). We also show that the isomorphism problem of Sd-graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute a simple FPT-time combinatorial algorithm for isomorphism testing in the special case of proper Sd- and T-graphs.