View publication

Title Navigating Planar Topologies in Near-Optimal Space and Time
Authors JosĂ© Fuentes-SepĂșlveda, Gonzalo Navarro, Diego Seco
Publication date 2023
Abstract 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). Indeed, 3.58m + o(m) bits suffice if the graph has no self-loops
and no nodes of degree one. Further, we show that with O(m) bits of space we
can solve all those operations in O(1) time.
Pages article 101922
Volume 109
Journal name Computational Geometry Theory and Applications
Publisher Elsevier Science (Amsterdam, The Netherlands)
Reference URL View reference page