Abstract
A circular-arc model ℳ is a circle C together with a collection \(\mathcal{A}\) of arcs of C. If \(\mathcal{A}\) satisfies the Helly Property then ℳ is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n 3). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Benzer, S.: On the topology of the genetic fine structure. Proc. Natl. Acad. Sci. USA 45, 1607–1620 (1959)
Booth, S., Lueker, S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335–379 (1976)
Deng, X., Hell, P., Huang, J.: Linear time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J. Comput. 25, 390–403 (1996)
Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209–221 (1985)
Gavril, F.: Algorithms on circular-arc graphs. Networks 4, 357–369 (1974)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Academic Press, New York (2004)
Habib, M., McConnell, R., Paul, C., Viennot, L.: Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234, 59–84 (2000)
Itai, A.: Linear time restricted union/find. Manuscript (2006)
Kaplan, H., Nussbaum, Y.: A simpler linear-time recognition of circular-arc graphs. In: The Tenth Scandinavian Workshop on Algorithm Theory (SWAT’06). Lecture Notes in Computer Science, vol. 4059, pp. 289–300. Springer, Berlin (2006)
Kaplan, H., Nussbaum, Y.: Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs. In: Proceedings of the 32nd Workshop on Graph Theoretic Concepts in Computer Science (WG’06). Lecture Notes in Computer Science, vol. 4271, pp. 289–300. Springer, Berlin (2006)
Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley, Boston (2006)
Lekkerker, C.G., Boland, J.C.: Representation of finite graphs by a set of intervals on the real line. Fund. Math. 51, 45–64 (1962)
Lin, M.C., Szwarcfiter, J.L.: Characterizations and linear time recognition of Helly circular-arc graphs. In: Proceedings of the 12th Annual International Conference on Computing and Combinatorics (COCOON’06). Lecture Notes in Computer Science, vol. 4112, pp. 73–82. Springer, Berlin (2006)
Lin, M.C., Szwarcfiter, J.L.: Efficient construction of unit circular-arc models. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’06), pp. 309–315 (2006)
Lin, M.C., Szwarcfiter, J.L.: Unit circular-arc graph representations and feasible circulations. SIAM J. Discrete Math. 22, 409–423 (2008)
McConnell, R.M.: Linear-time recognition of circular-arc graphs. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS’01), pp. 386–394 (2001)
McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica 37(2), 93–147 (2003)
Roberts, F.S.: Graph Theory and its Applications to Problems of Society. Society for Industrial and Applied Mathematics, Philadelphia (1978)
Spinrad, J.: Efficient Graph Representations. Am. Math. Soc., Providence (2003)
Tucker, A.: Characterizing circular-arc graphs. Bull. Am. Math. Soc. 76, 1257–1260 (1970)
Tucker, A.: An efficient test for circular-arc graphs. SIAM J. Comput. 9, 1–24 (1980)
Author information
Authors and Affiliations
Corresponding author
Additional information
M.C. Lin was partially supported by UBACyT Grants X456 and X143 and by PICT ANPCyT Grant 1562.
J.L. Szwarcfiter was partially supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq, and Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro, FAPERJ, Brasil.
Rights and permissions
About this article
Cite this article
Joeris, B.L., Lin, M.C., McConnell, R.M. et al. Linear-Time Recognition of Helly Circular-Arc Models and Graphs. Algorithmica 59, 215–239 (2011). https://doi.org/10.1007/s00453-009-9304-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-009-9304-5