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.ESA.2016.70
URN: urn:nbn:de:0030-drops-64120
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6412/
Go to the corresponding LIPIcs Volume Portal

Neuen, Daniel

Graph Isomorphism for Unit Square Graphs

pdf-format:
LIPIcs-ESA-2016-70.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{neuen:LIPIcs:2016:6412,
  author =	{Daniel Neuen},
  title =	{{Graph Isomorphism for Unit Square Graphs}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{70:1--70:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6412},
  URN =		{urn:nbn:de:0030-drops-64120},
  doi =		{10.4230/LIPIcs.ESA.2016.70},
  annote =	{Keywords: graph isomorphism, geometric graphs, unit squares}
}

Keywords: graph isomorphism, geometric graphs, unit squares
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

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