Recognizing Optimal 1-Planar Graphs in Linear Time
Recognizing Optimal 1-Planar Graphs in Linear Time
复制标题
识别线性时间内的最优一平面图
DOI：
10.1007/s00453-016-0226-8
复制
发表时间：
--
期刊：
影响因子：
1.1
通讯作者：
F. J. Brandenburg
中科院分区：
文献类型：
--
作者：
F. J. Brandenburg
一个顶点数为n的图是1-平面的，如果它能在平面上画出，使得每条边至多相交一次，并且如果它有最大的边，则它是最优的。我们发现，最佳1-平面图可以在线性时间内识别。我们的算法实现了一个具有两个规则的图约简系统，它可以用来将每个最优1-平面图约简为一个不可约的扩展轮图。图约简系统是不确定的、有约束的、非融合的。
A graph withnvertices is 1-planar if it can be drawn in the plane such that each edge is crossed at most once, and is optimal if it has the maximum ofedges. We show that optimal 1-planar graphs can be recognized in linear time. Our algorithm implements a graph reduction system with two rules, which can be used to reduce every optimal 1-planar graph to an irreducible extended wheel graph. The graph reduction system is non-deterministic, constraint, and non-confluent.
登录
查看更多内容
平面度测试和嵌入
DOI：
--
发表时间：
2013
期刊：
Handbook of Graph Drawing and Visualization
影响因子：
--
作者：
M. Patrignani
通讯作者：
M. Patrignani
扇形平面图：组合属性和复杂性结果
DOI：
--
发表时间：
2014
期刊：
International Symposium Graph Drawing and Network Visualization
影响因子：
--
作者：
Carla Binucci;E. D. Giacomo;W. Didimo;Fabrizio Montecchiani;M. Patrignani;I. Tollis
通讯作者：
I. Tollis
识别立方时间内的无孔 4 映射图
DOI：
--
发表时间：
2006
期刊：
Algorithmica 45(2)
影响因子：
--
作者：
Zhi-Zhong Chen;Michelangelo Grigni;Christos H. Papadimitriou
通讯作者：
Christos H. Papadimitriou
最优一平面图的约简系统
DOI：
--
发表时间：
2016
期刊：
arXiv.org
影响因子：
--
作者：
F. Brandenburg
通讯作者：
F. Brandenburg
论扇形平面和最大外扇形平面图的识别
影响因子：
1.1
作者：
M. Bekos;Sabine Cornelsen;L. Grilli;Seok;M. Kaufmann
通讯作者：
M. Kaufmann