It is known that the vertex connectivity of a planar graph can be computed in linear time. We extend this result to the class of locally maximal 1-plane graphs: graphs that have an embedding with at most one crossing per edge such that the endpoints of each pair of crossing edges induce the complete graph $K_4$
翻译：众所周知,平面图的顶点连接可以用线性时间计算。我们将这一结果扩展至本地最大1平面图:每个边缘最多嵌入一个交叉点的图形,以便每对跨越边缘的终点引出完整的图形 $K_4$
相关内容
Arxiv
0+阅读 · 2022年2月16日
Arxiv
0+阅读 · 2022年2月14日
Arxiv
0+阅读 · 2022年2月14日
相关VIP内容
相关资讯
相关论文
Arxiv
0+阅读 · 2022年2月16日
Arxiv
0+阅读 · 2022年2月14日
Arxiv
0+阅读 · 2022年2月14日
微信扫码咨询专知VIP会员