We consider the problem of determining if a pair of undirected graphs $\langle G_\mathsf{V}, G_\mathsf{H} \rangle$, which share the same vertex set, has a representation using opaque geometric shapes for vertices, and vertical/horizontal visibility between shapes to determine the edges of $G_\mathsf{V}$/$G_\mathsf{H}$. While such a simultaneous visibility representation of two graphs can be determined efficiently if the direction of the required visibility for each edge is provided (and the vertex shapes are sufficiently simple), it was unclear if edge direction is critical for efficiency. We show that the problem is $\mathsf{NP}$-complete without that information, even for graphs that are only slightly more complex than paths. In addition, we characterize which pairs of paths have simultaneous visibility representations using fixed orientation L-shapes. This narrows the range of possible graph families for which determining simultaneous visibility representation is non-trivial yet not $\mathsf{NP}$-hard.


翻译:我们考虑的问题是如何确定一对非方向图形 $\ langle G ⁇ mathsf{V}, G ⁇ mathsf{H}\rangle$, 共使用相同的顶点设置, 是否使用不透明的脊椎几何形状表示, 以及形状之间的垂直/ 横向可见度, 以确定 $G ⁇ mathsf{V}$/ $G ⁇ mathsf{H} 的边缘。 如果提供每个边缘所需的可见度方向( 而顶点形状足够简单), 则可以有效确定两个图的同步可见度代表。 我们显示, 问题在于没有这种信息的情况下, $\ mathsf{NP} $ 问题是完全的, 即使是那些只比路径略复杂一点的图形。 此外, 我们用固定方向 L- shape 来辨别哪些路径配有同步可见度表示。 这缩小了可能用来确定同步可见度表示值的图形家庭的范围 。

0
下载
关闭预览

相关内容

知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
163+阅读 · 2020年3月18日
【康奈尔大学】度量数据粒度,Measuring Dataset Granularity
专知会员服务
12+阅读 · 2019年12月27日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
已删除
将门创投
4+阅读 · 2017年12月5日
Arxiv
0+阅读 · 2021年7月15日
Arxiv
0+阅读 · 2021年7月15日
Arxiv
0+阅读 · 2021年7月12日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
已删除
将门创投
4+阅读 · 2017年12月5日
Top
微信扫码咨询专知VIP会员