Graph Isomorphism for Unit Square Graphs
Graph Isomorphism for Unit Square Graphs
复制标题
单位平方图的图同构
DOI：
10.4230/lipics.esa.2016.70
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Daniel Neuen
中科院分区：
文献类型：
--
作者：
Daniel Neuen
在过去的几十年中，越来越多的图类的图同构问题被证明可以在多项式时间内解决。一系列有趣的图类源自几何对象的交集图。在这项工作中，我们证明了单位正方形图（平面上轴平行单位正方形的交图）的图同构问题可以在多项式时间内求解。由于此类图的识别问题是 NP 困难的，我们不能依赖基于构建规范实现的几何图标准技术。相反，我们开发了新技术，将单位方形图类的结构见解与对此类图的自同构群的理解结合起来。对于后者，我们引入了有界度图的推广，用于捕获单位方形图的主要结构。使用群论算法，我们获得足够的信息来解决单位方形图的同构问题。
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.
捕获区间图上的多项式时间
DOI：
10.1109/lics.2010.42
发表时间：
2010
期刊：
2010 25th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
B. Laubner
通讯作者：
B. Laubner
解决对数空间中适当圆弧图的规范表示和星系统问题
DOI：
10.1016/j.jda.2016.03.001
发表时间：
2016
期刊：
影响因子：
--
作者：
J. Köbler;S. Kuhnert;O. Verbitsky
通讯作者：
O. Verbitsky
区间图：对数空间中的规范表示
DOI：
10.1137/10080395x
发表时间：
2011
期刊：
SIAM J. Comput.
影响因子：
--
作者：
J. Köbler;S. Kuhnert;B. Laubner;O. Verbitsky
通讯作者：
O. Verbitsky