On the isomorphism problem for Helly circular-arc graphs.
With Johannes Köbler, Oleg Verbitsky.
Information and Computation 247:266–277 (2016)

Abstract. We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Δ trees employed in McConnell’s linear time representation algorithm for interval matrices are adapted to the logspace setting and endowed with additional information to allow canonization. As a consequence, the isomorphism and recognition problems for HCA graphs turn out to be logspace complete.

Conference version:
Helly Circular-Arc Graph Isomorphism is in logspace
With Johannes Köbler, Oleg Verbitsky.
Mathematical Foundations of Computer Science (Proceedings of 38th MFCS). Springer, 2013. Pp. 631–642.