Other formats:
BibTeX
LaTeX
RIS
@inproceedings{2294854,
author = {Agaoglu Cagirici, Deniz and Cagirici, Onur and Derbisz, Jan and Hartmann, Tim and Hliněný, Petr and Kratochvíl, Jan and Krawczyk, Tomasz and Zeman, Peter},
address = {Dagstuhl, Germany},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
doi = {http://dx.doi.org/10.4230/LIPIcs.MFCS.2023.8},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
keywords = {H-graphs; Intersection Graphs; Helly Property},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Dagstuhl, Germany},
isbn = {978-3-95977-292-1},
pages = {"8:1"-"8:14"},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
title = {Recognizing H-Graphs - Beyond Circular-Arc Graphs},
year = {2023}
}
TY - JOUR
ID - 2294854
AU - Agaoglu Cagirici, Deniz - Cagirici, Onur - Derbisz, Jan - Hartmann, Tim - Hliněný, Petr - Kratochvíl, Jan - Krawczyk, Tomasz - Zeman, Peter
PY - 2023
TI - Recognizing H-Graphs - Beyond Circular-Arc Graphs
PB - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
CY - Dagstuhl, Germany
SN - 9783959772921
KW - H-graphs
KW - Intersection Graphs
KW - Helly Property
N2 - In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph H, the class of H-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of H. Such classes of graphs are related to many known graph classes: for example, K₂-graphs coincide with interval graphs, K₃-graphs with circular-arc graphs, the union of T-graphs, where T ranges over all trees, coincides with chordal graphs. Recently, quite a lot of research has been devoted to understanding the tractability border for various computational problems, such as recognition or isomorphism testing, in classes of H-graphs for different graphs H. In this work we undertake this research topic, focusing on the recognition problem. Chaplick, Töpfer, Voborník, and Zeman showed an XP-algorithm testing whether a given graph is a T-graph, where the parameter is the size of the tree T. In particular, for every fixed tree T the recognition of T-graphs can be solved in polynomial time. Tucker showed a polynomial time algorithm recognizing K₃-graphs (circular-arc graphs). On the other hand, Chaplick et al. showed also that for every fixed graph H containing two distinct cycles sharing an edge, the recognition of H-graphs is NP-hard. The main two results of this work narrow the gap between the NP-hard and 𝖯 cases of H-graph recognition. First, we show that the recognition of H-graphs is NP-hard when H contains two distinct cycles. On the other hand, we show a polynomial-time algorithm recognizing L-graphs, where L is a graph containing a cycle and an edge attached to it (which we call lollipop graphs). Our work leaves open the recognition problems of M-graphs for every unicyclic graph M different from a cycle and a lollipop.
ER -
AGAOGLU CAGIRICI, Deniz, Onur CAGIRICI, Jan DERBISZ, Tim HARTMANN, Petr HLINĚNÝ, Jan KRATOCHVÍL, Tomasz KRAWCZYK and Peter ZEMAN. Recognizing H-Graphs - Beyond Circular-Arc Graphs. Online. In Leroux, J$\backslash$'$\{$e$\}$r$\backslash$\^{}$\{$o$\}$me and Lombardy, Sylvain and Peleg, David. \textit{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f$\{\backslash$''u$\}$r Informatik, 2023, p.~''8:1''-''8:14'', 14 pp. ISBN~978-3-95977-292-1. Available from: https://dx.doi.org/10.4230/LIPIcs.MFCS.2023.8.
|
