Graph isomorphism for unit square graphs

DOI10.4230/LIPICS.ESA.2016.70MaRDI QIDQ4606343zbMATH OpenOpenAlexFDO

Authors Daniel Neuen

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1602.08371

zbMATH Keywords

graph isomorphismgeometric graphsunit squares

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph representations (geometric and intersection representations, etc.) (05C62)

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.

Recommendations

• The graph isomorphism problem on geometric graphs
• Graph isomorphism and equality of simplices
• A geometric approach to graph isomorphism
• Combinatorial properties and recognition of unit square visibility graphs
• On the geometric graph isomorphism problem

Cited in

(8)

• The graph isomorphism problem on geometric graphs
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
• Isomorphism testing for graphs excluding small topological subgraphs
• An improved isomorphism test for bounded-tree-width graphs
• Unit ball graphs on geodesic spaces
• The power of the Weisfeiler-Leman algorithm to decompose graphs
• Hypergraph isomorphism for groups with restricted composition factors

This page was built for publication: Graph isomorphism for unit square graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606343)