On the isomorphism problem for Helly circular-arc graphs

DOI10.1016/J.IC.2016.01.006MaRDI QIDQ259081zbMATH OpenOpenAlexFDO

Authors Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

Publication date 10 March 2016

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

circular-arc graphsgraph isomorphismgraph representationHelly propertylogarithmic space

Mathematics Subject Classification ID

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

Abstract: The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular arcs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal.

Recommendations

• Helly circular-arc graph isomorphism is in logspace
• scientific article; zbMATH DE number 6829367
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Linear-time recognition of Helly circular-arc models and graphs
• Around and beyond the isomorphism problem for interval graphs

Cites work

• scientific article; zbMATH DE number 3737705 (Why is no real title available?)
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Algorithms on circular-arc graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Efficient graph representations
• Helly circular-arc graph isomorphism is in logspace
• Incidence matrices and interval graphs
• Interval graph representation with given interval and intersection lengths
• Interval graphs: canonical representations in logspace
• Isomorphism of graph classes related to the circular-ones property
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time recognition of Helly circular-arc models and graphs
• Linear-time recognition of circular-arc graphs
• On the Hardness of Graph Isomorphism
• Parallel recognition of the consecutive ones property with applications
• Simple Geometrical Intersection Graphs
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Topics in Intersection Graph Theory
• Tractabilities and intractabilities on geometric intersection graphs

Cited in

(6)

• Hadwiger's conjecture for proper circular arc graphs
• Around and beyond the isomorphism problem for interval graphs
• Helly circular-arc graph isomorphism is in logspace
• Isomorphism of graph classes related to the circular-ones property
• Essential obstacles to Helly circular-arc graphs
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs

This page was built for publication: On the isomorphism problem for Helly circular-arc graphs

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