2026-08-16T23:51:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4940 2024-03-06T10:35:35Z ddc:004 open_access

Automorphism Groups of Geometrically Represented Graphs Klavík­, Pavel Zeman, Peter automorphism group geometric intersection graph interval graph circle graph Interval graphs are intersection graphs of closed intervals and circle graphs are intersection graphs of chords of a circle. We study automorphism groups of these graphs. We show that interval graphs have the same automorphism groups as trees, and circle graphs have the same as pseudoforests, which are graphs with at most one cycle in every connected component. Our technique determines automorphism groups for classes with a strong structure of all geometric representations, and it can be applied to other graph classes. Our results imply polynomial-time algorithms for computing automorphism groups in term of group products. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pavel Klavík­ and Peter Zeman 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.540 urn:nbn:de:0030-drops-49408 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.540 eng https://creativecommons.org/licenses/by/3.0/legalcode