*BibTeX*

@Article{KKV16pca, author = {Johannes Köbler and Sebastian Kuhnert and Oleg Verbitsky}, title = {Solving the canonical representation and star system problems for proper circular-arc graphs in logspace}, journal = {Journal of Discrete Algorithms}, year = 2016, volume = {38-41}, pages = {38-49}, issn = {1570-8667}, doi = {10.1016/j.jda.2016.03.001}, }

**Solving the canonical
representation and star system problems for proper circular-arc
graphs in logspace.**

With Johannes
Köbler, Oleg
Verbitsky.

*Journal of Discrete Algorithms* 38–41:38–49 (2016)

Abstract.We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where /canonical/ means that isomorphic graphs receive identical models. This implies that the recognition and the isomorphism problems for these graphs are solvable in logspace. For the broader class of concave-round graphs, which still possess (not necessarily proper) circular-arc models, we show that a canonical circular-arc model can also be constructed in logspace. As a building block for these results, we design a logspace algorithm for computing canonical circular-arc models of circular-arc hypergraphs. This class of hypergraphs corresponds to matrices with the /circular ones property/, which play an important role in computational genomics. Our results imply that there is a logspace algorithm that decides whether a given matrix has this property.

Furthermore, we consider the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We show that this problem is solvable in logarithmic space for the classes of proper circular-arc, concave-round, and co-convex graphs.

Note that solving a problem in logspace implies that it is solvable by a parallel algorithm of the class AC¹. For the problems under consideration, at most AC² algorithms were known earlier.

*BibTeX*

@InProceedings{KKV12pca, author = {Johannes Köbler and Sebastian Kuhnert and Oleg Verbitsky}, title = {Solving the canonical representation and star system problems for proper circular-arc graphs in logspace}, booktitle = {Proc. 32nd FSTTCS}, pages = {387-399}, year = 2012, editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan}, series = {LIPIcs}, number = 18, publisher = {Leibniz-Zentrum für Informatik}, address = {Dagstuhl}, isbn = {978-3-939897-47-7}, doi = {10.4230/LIPIcs.FSTTCS.2012.387}, }

Conference version:

**Solving the canonical representation and star system
problems for proper circular-arc graphs in logspace**

With Johannes
Köbler, Oleg
Verbitsky.

*Proceedings of 32nd FSTTCS.*
Leibniz-Zentrum für Informatik, 2012. Pp. 387–399.