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 来辨别哪些路径配有同步可见度表示。 这缩小了可能用来确定同步可见度表示值的图形家庭的范围 。