Document Open Access Logo

Automorphism Groups of Geometrically Represented Graphs

Authors Pavel Klavík­, Peter Zeman

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.540.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Author Details

Pavel Klavík­
Peter Zeman

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.STACS.2015.540

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.
Keywords
  • automorphism group
  • geometric intersection graph
  • interval graph
  • circle graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. L. Babai. Automorphism groups of planar graphs II. In Infinite and finite sets (Proc. Conf. Kestzthely, Hungary), 1973. Google Scholar
  2. K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and planarity using PQ-tree algorithms. J. Comput. System Sci., 13:335-379, 1976. Google Scholar
  3. N. Carter. Visual group theory. MAA, 2009. Google Scholar
  4. C. J. Colbourn and K. S. Booth. Linear times automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput., 10(1):203-225, 1981. Google Scholar
  5. Derek G Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, and Alan P Sprague. Simple linear time recognition of unit interval graphs. Information Processing Letters, 55(2):99-104, 1995. Google Scholar
  6. W.H. Cunningham. Decomposition of directed graphs. SIAM Journal on Algebraic Discrete Methods, 3:214-228, 1982. Google Scholar
  7. P. Erdös, S. Fajtlowicz, and A. J. Hoffman. Maximum degree in graphs of diameter 2. Networks, 10(1):87-90, 1980. Google Scholar
  8. J. Fiala, P. Klavík, J. Kratochvíl, and R. Nedela. Algorithmic aspects of regular graphs covers with applications to planar graphs. In Lecture Notes in Computer Science, Automata, Languages, and Programming ICALP 2014, volume 8572, pages 489-501, 2014. Google Scholar
  9. R. Frucht. Herstellung von graphen mit vorgegebener abstrakter gruppe. Compositio Mathematica, 6:239-250, 1939. Google Scholar
  10. D. R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs. Pac. J. Math., 15:835-855, 1965. Google Scholar
  11. C. P. Gabor, K. J. Supowit, and W.-L. Hsu. Recognizing circle graphs in polynomial time. Journal of the ACM (JACM), 36(3):435-473, 1989. Google Scholar
  12. E. Gioan and C. Paul. Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs. Discrete Appl. Math., 160(6):708-733, 2012. Google Scholar
  13. E. Gioan, C. Paul, M. Tedder, and D. Corneil. Practical and efficient circle graph recognition. Algorithmica, pages 1-30, 2013. Google Scholar
  14. C. D. Godsil and G. Royle. Algebraic graph theory, volume 207. Springer New York, 2001. Google Scholar
  15. M. C. Golumbic. Algorithmic graph theory and perfect graphs, volume 57. Elsevier, 2004. Google Scholar
  16. M. Grohe and D. Marx. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 173-192, 2012. Google Scholar
  17. P. Hanlon. Counting interval graphs. Transactions of the American Mathematical Society, 272(2):383-426, 1982. Google Scholar
  18. Z. Hedrlín, A. Pultr, et al. On full embeddings of categories of algebras. Illinois Journal of Mathematics, 10(3):392-406, 1966. Google Scholar
  19. A. J. Hoffman and R. R. Singleton. On moore graphs with diameters 2 and 3. IBM Journal of Research and Development, 4(5):497-504, 1960. Google Scholar
  20. W. L. Hsu. 𝒪(M ⋅ N) algorithms for the recognition and isomorphism problems on circular-arc graphs. SIAM Journal on Computing, 24(3):411-439, 1995. Google Scholar
  21. C. Jordan. Sur les assemblages de lignes. Journal für die reine und angewandte Mathematik, 70:185-190, 1869. Google Scholar
  22. N. Korte and R. H. Möhring. An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput., 18(1):68-81, 1989. Google Scholar
  23. G. S. Lueker and K. S. Booth. A linear time algorithm for deciding interval graph isomorphism. Journal of the ACM (JACM), 26(2):183-195, 1979. Google Scholar
  24. E. M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42-65, 1982. Google Scholar
  25. R. Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8(3):131-136, 1979. Google Scholar
  26. B. D. McKay, M. Miller, and J. Širáň. A note on large graphs of diameter two and given maximum degree. J. Combin. Theory Ser. B, 74(1):110-118, 1998. Google Scholar
  27. M. Miller and J. Širáň. Moore graphs and beyond: A survey of the degree/diameter problem. Electronic Journal of Combinatorics, 61:1-63, 2005. Google Scholar
  28. Fred S Roberts. Indifference graphs. Proof techniques in graph theory, 139:146, 1969. Google Scholar
  29. J. J. Rotman. An introduction to the theory of groups, volume 148. Springer, 1995. Google Scholar
  30. U. Schöning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37(3):312-323, 1988. Google Scholar
  31. J. P. Spinrad. Efficient Graph Representations.: The Fields Institute for Research in Mathematical Sciences., volume 19. American Mathematical Soc., 2003. Google Scholar
  32. H. Whitney. Nonseparable and planar graphs. Trans. Amer. Math. Soc., 34:339-362, 1932. Google Scholar
  33. Mihalis Yannakakis. The complexity of the partial order dimension problem. SIAM Journal on Algebraic Discrete Methods, 3(3):351-358, 1982. Google Scholar
  34. S. Zhou. A class of arc-transitive Cayley graphs as models for interconnection networks. SIAM Journal on Discrete Mathematics, 23(2):694-714, 2009. Google Scholar
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