Dynamic Compact Planar Embeddings

Abstract

This thesis presents a way to compactly represent dynamic connected planar embeddings, which may contain self loops and multi-edges, in 4m + o(m) bits, to support basic navigation in O(lg n) time and edge and vertex insertion and deletion in O(lg^(1+ϵ) n) time, where n and m are respectively the number of vertices and edges currently in the graph and ϵ is an arbitrary positive constant. Previous works on dynamic succinct planar graphs either do not provide a full set of update operations or are restricted to triangulations where the outer face must be a simple polygon and all inner faces must be triangles. To the best of our knowledge, this thesis presents the first representation of dynamic compact connected planar embeddings that supports a full set of dynamic operations without restrictions on the sizes or shapes of the faces.