2026-09-22T03:10:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24989 2026-09-05T19:01:33Z ddc:004 open_access

On the Structure of Normalized Models of Circular-Arc Graphs I. Hsu’s Approach Krawczyk, Tomasz intersection graphs and models circular-arc graphs and circular-arc intersection models In the work [𝒪(m⋅ n) algorithms for the recognition and isomorphism problems on circular-arc graphs, SIAM J. Comput. 24(3), 411-439, (1995)], Wen-Lian Hsu claims three results concerning the class of circular-arc graphs: - the design of so-called decomposition trees that represent the structure of all normalized intersection models of circular-arc graphs, - an 𝒪(nm)-time recognition algorithm for circular-arc graphs, - an 𝒪(nm)-time isomorphism algorithm for circular-arc graphs. In [Discrete Math. Theor. Comput. Sci., 15(1), 157-182, 2013] Curtis, Lin, McConnell, Nussbaum, Soulignac, Spinrad, and Szwarcfiter showed that Hsu’s isomorphism algorithm is incorrect. In this note, we show that the other two results - namely, the construction of decomposition trees and the recognition algorithm - are also flawed. We also present the main ideas that made it possible to construct a data structure that maintains normalized models of circular-arc graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomasz Krawczyk 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.3 urn:nbn:de:0030-drops-249892 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.3 eng https://creativecommons.org/licenses/by/4.0/legalcode