License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.540
URN: urn:nbn:de:0030-drops-49408
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4940/
Go to the corresponding LIPIcs Volume Portal

Klavík­, Pavel ; Zeman, Peter

Automorphism Groups of Geometrically Represented Graphs

pdf-format:
40.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{klavk_et_al:LIPIcs:2015:4940,
  author =	{Pavel Klav{\'i}k­ and Peter Zeman},
  title =	{{Automorphism Groups of Geometrically Represented Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{540--553},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4940},
  URN =		{urn:nbn:de:0030-drops-49408},
  doi =		{10.4230/LIPIcs.STACS.2015.540},
  annote =	{Keywords: automorphism group, geometric intersection graph, interval graph, circle graph}
}

Keywords: automorphism group, geometric intersection graph, interval graph, circle graph
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI