###
Navigating Planar Topologies in Near-Optimal Space and Time

####
José Fuentes-Sepúlveda, Gonzalo Navarro, and Diego Seco

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 4*m* bits, which is close to the
information-theoretic lower bound of about 3.58*m*. With 4*m* +
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
ω(1). Indeed, 3.58*m* + 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.