论文标题
地形可见性图：持久性还不够
Terrain Visibility Graphs: Persistence is Not Enough
论文作者
论文摘要
在本文中，我们考虑了地形背景下的可见性图形识别和重建问题。在这里，我们获得了一个图形$ g $，带有标记的顶点$ v_0，v_1，\ ldots，v_ {n-1} $，使标签与哈密顿路径$ h $相对应。 $ g $也可能包含其他边缘。我们有兴趣确定是否有一个Terrain $ t $，带有顶点$ p_0，p_1，\ ldots，p_ {n-1} $，使$ g $是$ t $的可见度图，$ t $的边界与$ h $相对应。据说$ g $在且仅当它满足所谓的X-Property和Bar-Property时才持久。众所周知，每个“伪terrain”都有一个持久的可见性图，并且每个持久图都是某些伪terrain的可见性图。对于（几何）地形而言，连接并不清楚。众所周知，任何地形$ t $的可见度图都是持久的，但是尚不清楚每个持久图$ g $是否具有地形$ t $，因此$ g $是$ t $的可见度图。实际上，有几篇论文声称是这种情况（尽管从未出版过正式的证据），并且最近的作品为任何持久图构建地形重建算法做出了步骤。在本文中，我们表明存在一个持久的图$ g $，这不是任何地形$ t $的可见度图。这意味着持久性本身还不足以表征地形的可见性图，这意味着伪鸟无法拉伸。
In this paper, we consider the Visibility Graph Recognition and Reconstruction problems in the context of terrains. Here, we are given a graph $G$ with labeled vertices $v_0, v_1, \ldots, v_{n-1}$ such that the labeling corresponds with a Hamiltonian path $H$. $G$ also may contain other edges. We are interested in determining if there is a terrain $T$ with vertices $p_0, p_1, \ldots, p_{n-1}$ such that $G$ is the visibility graph of $T$ and the boundary of $T$ corresponds with $H$. $G$ is said to be persistent if and only if it satisfies the so-called X-property and Bar-property. It is known that every "pseudo-terrain" has a persistent visibility graph and that every persistent graph is the visibility graph for some pseudo-terrain. The connection is not as clear for (geometric) terrains. It is known that the visibility graph of any terrain $T$ is persistent, but it has been unclear whether every persistent graph $G$ has a terrain $T$ such that $G$ is the visibility graph of $T$. There actually have been several papers that claim this to be the case (although no formal proof has ever been published), and recent works made steps towards building a terrain reconstruction algorithm for any persistent graph. In this paper, we show that there exists a persistent graph $G$ that is not the visibility graph for any terrain $T$. This means persistence is not enough by itself to characterize the visibility graphs of terrains, and implies that pseudo-terrains are not stretchable.
