Search Results

Documents authored by Klavík­, Pavel

Document
DOI: 10.4230/LIPIcs.STACS.2015.540
Automorphism Groups of Geometrically Represented Graphs

Authors: Pavel Klavík­ and Peter Zeman

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

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.
Cite as

Pavel Klavík­ and Peter Zeman. Automorphism Groups of Geometrically Represented Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 540-553, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{klavik_et_al:LIPIcs.STACS.2015.540,
  author =	{Klav{\'\i}k­, Pavel and Zeman, Peter},
  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 =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.540},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact