Canonical representations for circular-arc graphs using flip sets

DOI10.1007/S00453-018-0410-0MaRDI QIDQ1799215zbMATH OpenOpenAlexFDO

Publication date 18 October 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.05763

circular-arc graphs isomorphism canonization

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We show that computing canonical representations for circular-arc (CA) graphs reduces to computing certain subsets of vertices called flip sets. For a broad class of CA graphs, which we call uniform, it suffices to compute a CA representation to find such flip sets. As a consequence canonical representations for uniform CA graphs can be obtained in polynomial-time. We then investigate what kind of CA graphs pose a challenge to this approach. This leads us to introduce the notion of restricted CA matrices and show that the canonical representation problem for CA graphs is logspace-reducible to that of restricted CA matrices. As a byproduct, we obtain the result that CA graphs without induced 4-cycles can be canonized in logspace.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Canonical representations for circular-arc graphs using flip sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1799215)