Document Open Access Logo

Graph Isomorphism for Unit Square Graphs

Author Daniel Neuen

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.70.pdf
  • Filesize: 0.52 MB
  • 17 pages

Document Identifiers

Author Details

Daniel Neuen

Cite As Get BibTex

Daniel Neuen. Graph Isomorphism for Unit Square Graphs. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 70:1-70:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.70

Abstract

In the past decades for more and more graph classes the Graph Isomorphism Problem was shown to be solvable in polynomial time. An interesting family of graph classes arises from intersection graphs of geometric objects. In this work we show that the Graph Isomorphism Problem for unit square graphs, intersection graphs of axis-parallel unit squares in the plane, can be solved in polynomial time. Since the recognition problem for this class of graphs is NP-hard we can not rely on standard techniques for geometric graphs based on constructing a canonical realization. Instead, we develop new techniques which combine structural insights into the class of unit square graphs with understanding of the automorphism group of such graphs. For the latter we introduce a generalization of bounded degree graphs which is used to capture the main structure of unit square graphs. Using group theoretic algorithms we obtain sufficient information to solve the isomorphism problem for unit square graphs.

Subject Classification

Keywords
  • graph isomorphism
  • geometric graphs
  • unit squares

Metrics

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

References

  1. László Babai. On the automorphism groups of strongly regular graphs I. In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 359-368. ACM, 2014. URL: http://dl.acm.org/citation.cfm?id=2554797, URL: http://dx.doi.org/10.1145/2554797.2554830.
  2. László Babai. Graph isomorphism in quasipolynomial time. CoRR, abs/1512.03547, 2015. URL: http://arxiv.org/abs/1512.03547.
  3. László Babai, Peter J. Cameron, and Péter P. Pálfy. On the orders of primitive groups with restricted nonabelian composition factors. Journal of Algebra, 79(1):161-168, 1982. URL: http://dx.doi.org/10.1016/0021-8693(82)90323-4.
  4. László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, and John Wilmes. Faster canonical forms for strongly regular graphs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 157-166. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.25.
  5. László Babai, William M. Kantor, and Eugene M. Luks. Computational complexity and the classification of finite simple groups. In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, pages 162-171. IEEE Computer Society, 1983. URL: http://dx.doi.org/10.1109/SFCS.1983.10.
  6. Christoph Berkholz, Paul S. Bonsma, and Martin Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, volume 8125 of Lecture Notes in Computer Science, pages 145-156. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_13.
  7. Heinz Breu. Algorithmic Aspects of Constrained Unit Disk Graphs. PhD thesis, University of British Columbia, Vancouver, Canada, 1996. Google Scholar
  8. Heinz Breu and David G. Kirkpatrick. Unit disk graph recognition is np-hard. Comput. Geom., 9(1-2):3-24, 1998. URL: http://dx.doi.org/10.1016/S0925-7721(97)00014-X.
  9. Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992. URL: http://dx.doi.org/10.1007/BF01305232.
  10. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1-3):165-177, 1990. URL: http://dx.doi.org/10.1016/0012-365X(90)90358-O.
  11. Charles J. Colbourn and Kellogg S. Booth. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput., 10(1):203-225, 1981. URL: http://dx.doi.org/10.1137/0210015.
  12. Andrew R. Curtis, Min Chih Lin, Ross M. McConnell, Yahav Nussbaum, Francisco J. Soulignac, Jeremy P. Spinrad, and Jayme Luiz Szwarcfiter. Isomorphism of graph classes related to the circular-ones property. Discrete Mathematics & Theoretical Computer Science, 15(1):157-182, 2013. URL: http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2298.
  13. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric graphs. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1563-1575. SIAM, 2012. URL: http://dx.doi.org/10.1137/1.9781611973099.
  14. Delbert R. Fulkerson and Oliver A. Gross. Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15(3):835-855, 1965. Google Scholar
  15. Martin C. Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57). North-Holland Publishing Co., Amsterdam, The Netherlands, 2004. Google Scholar
  16. Derek F. Holt, Bettina Eick, and Eamonn A. O'Brien. Handbook of Computational Group Theory. Discrete Mathematics and Its Applications. CRC Press, 2005. Google Scholar
  17. Jing Huang. On the structure of local tournaments. J. Comb. Theory, Ser. B, 63(2):200-221, 1995. URL: http://dx.doi.org/10.1006/jctb.1995.1016.
  18. Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, and Oleg Verbitsky. Interval graphs: Canonical representations in logspace. SIAM J. Comput., 40(5):1292-1315, 2011. URL: http://dx.doi.org/10.1137/10080395X.
  19. Johannes Köbler, Sebastian Kuhnert, and Oleg Verbitsky. Solving the canonical representation and star system problems for proper circular-arc graphs in logspace. In Deepak D'Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, volume 18 of LIPIcs, pages 387-399. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. URL: http://www.dagstuhl.de/dagpub/978-3-939897-47-7, URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.387.
  20. Johannes Köbler, Sebastian Kuhnert, and Oleg Verbitsky. Helly circular-arc graph isomorphism is in logspace. In Krishnendu Chatterjee and Jirí Sgall, editors, Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, volume 8087 of Lecture Notes in Computer Science, pages 631-642. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40313-2_56.
  21. Bastian Laubner. Capturing polynomial time on interval graphs. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11-14 July 2010, Edinburgh, United Kingdom, pages 199-208. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/LICS.2010.42.
  22. Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci., 25(1):42-65, 1982. URL: http://dx.doi.org/10.1016/0022-0000(82)90009-5.
  23. Eugene M. Luks. Permutation groups and polynomial-time computation. In Larry Finkelstein and William M. Kantor, editors, Groups And Computation, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 7-10, 1991, volume 11 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 139-176. DIMACS/AMS, 1991. URL: http://dimacs.rutgers.edu/Volumes/Vol11.html.
  24. Brendan D. McKay. Practical Graph Isomorphism. Congressus Numerantium, 30:45-87, 1981. Google Scholar
  25. Joseph J. Rotman. An Introduction to the Theory of Groups. Graduate Texts in Mathematics. Springer, 1995. Google Scholar
  26. Pascal Schweitzer. Towards an isomorphism dichotomy for hereditary graph classes. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 689-702. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://www.dagstuhl.de/dagpub/978-3-939897-78-1, URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.689.
  27. Ákos Seress. Permutation Group Algorithms:. Cambridge Tracts in Mathematics. Cambridge University Press, 2003. Google Scholar
  28. Alan Tucker. Structure theorems for some circular-arc graphs. Discrete Math., 7(1-2):167-195, 1974. URL: http://dx.doi.org/10.1016/S0012-365X(74)80027-0.
  29. Ryuhei Uehara. Simple geometrical intersection graphs. In Shin-Ichi Nakano and Md. Saidur Rahman, editors, WALCOM: Algorithms and Computation, Second International Workshop, WALCOM 2008, Dhaka, Bangladesh, February 7-8, 2008., volume 4921 of Lecture Notes in Computer Science, pages 25-33. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-77891-2_3.
  30. Ryuhei Uehara. The graph isomorphism problem on geometric graphs. Discrete Mathematics & Theoretical Computer Science, 16(2):87-96, 2014. URL: http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2528.
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 About DROPS Imprint Privacy Contact