论文标题
无向图对的同时可见性表示
Simultaneous Visibility Representations of Undirected Pairs of Graphs
论文作者
论文摘要
我们考虑确定一对无方向的图表$ \ langle g_ \ mathsf {v}，g_ \ mathsf {h} \ rangle $，共享相同的顶点集，具有相同的顶点集，具有使用不透明的几何形状，用于台面，以及垂直/水平/水平/水平的shapes，并确定shopes shapes of shapes of shapes， $ g_ \ mathsf {v} $/$ g_ \ mathsf {h} $。如果提供每个边缘所需的可见性（并且顶点形状非常简单），则可以有效地确定两个图的同时可见性表示，但尚不清楚边缘方向是否对效率至关重要。我们表明，问题是$ \ mathsf {np} $ - 没有这些信息，即使对于仅比路径更复杂的图形也是如此。另外，我们表征了哪些路径对使用固定方向L形状具有同时可见性表示。这范围缩小了确定同时可见性表示形式的可能的图形家族的范围，但不是$ \ m athsf {np} $ - 硬。
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.
