近最佳空间和时间规划地形学导航 (Navigating Planar Topologies in Near-Optimal Space and Time)

from arxiv, This research has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions H2020-MSCA-RISE-2015 BIRDS GA No. 690941. Conference version presented at SPIRE 2019

We show that any embedding of a planar graph can be encoded succinctly while efficiently answering a number of topological queries near-optimally. More precisely, we build on a succinct representation that encodes an embedding of $m$ edges within $4m$ bits, which is close to the information-theoretic lower bound of about $3.58m$. With $4m+o(m)$ bits of space, we show how to answer a number of topological queries relating nodes, edges, and faces, most of them in any time in $\omega(1)$. Further, we show that with $O(m)$ bits of space we can solve all those operations in $O(1)$ time.

翻译：我们显示,任何嵌入平面图的内容都可以简洁地编码,同时有效地回答几处近乎最理想的表面学问题。更准确地说,我们以简洁的表述方式为基础,在四百万美元的位数内编码嵌入一百万美元的边缘,这接近信息理论下限约3.58亿美元。只要有四百万美元加一百万美元的空间位数,我们就能够解答许多与节点、边缘和面孔有关的表面学问题,其中多数在任何时间以一美元计。此外,我们用一百万美元的空间来显示,用一百万美元的位数,我们可以用一美元的时间解答所有这些操作。