Succinct Planar Encoding with Minor Operations
share
Let G be an unlabeled planar and simple n-vertex graph. We present a succinct encoding of G that provides induced-minor operations, i.e., edge contraction and vertex deletions. Any sequence of such operations is processed in O(n) time. In addition, the encoding provides constant time per element neighborhood access and degree queries. Using optional hash tables the encoding additionally provides constant expected time adjacency queries as well as an edge-deletion operation (thus, all minor operations are supported) such that any number of such edge deletions are computed in O(n) expected time. Constructing the encoding requires O(n) bits and O(n) time. The encoding requires ℋ(n) + o(n) bits of space with ℋ(n) being the entropy of encoding a planar graph with n vertices. Our data structure is based on the recent result of Holm et al. [ESA 2017] who presented a linear time contraction data structure that allows to maintain parallel edges and works for labeled graphs, but uses O(n log n) bits of space. We combine the techniques used by Holm et al. with novel ideas and the succinct encoding of Blelloch and Farzan [CPM 2010] for arbitrary separable graphs. Our result partially answers the question raised by Blelloch and Farzan if their encoding can be modified to allow modifications of the graph.
READ FULL TEXT