

Planar Maps in 4 bits/edge  http://arxiv.org/abs/math/0104147 Last revised: 22nd December 2001  
 

In this paper graph has the most general sense, admitting loops and multiple edges. Graphs discussed here are assumed connected, unlabelled, undirected, and finite. A map is an embedding of a graph in the open plane; an embedding in the sphere is trivially viewed as a map.  
Existing map encodings neglect maps with loops. [Turán84] encodes maps without loops or multiple edges in asymptotically 4 bits/edge . [Keeler95] encodes maps without loops or degree1 vertices in 3 bits/edge. Shorter encodings exist [Chuang98] for even more specialised graphs.  
The scheme below encodes any map in 4 bits/edge and requires an (unrestricted) choice of spanning tree and directed root edge. Decoding recovers the map, spanning tree and root edge.  
Map
edges
are
undirected;
'directed
edge'
means
a
pair
composed
of
a
map
edge
and
a
direction.
'CW'
means
'clockwise';
'CCW'
means
'counterclockwise'.
The
empty
map
is
encoded
as
the
empty
bit
string. A map M with m > 0 edges is encoded as follows:  
1.  Choose a directed edge e_{M} as the root edge of M. 
2.  Choose a spanning tree S of M. An edge of M is a tree edge if it lies in S, a nontree edge if not. 
3.  Make a tree map T from M by splitting each nontree edge e in M into two labelled leaf edges; label with "[" (resp. "]") the new edge in T corresponding to the initial (resp. final) segment of e tracing CCW about the circuit made by e and elements of S. If e_{M} is a tree edge then the directed root edge e_{T} of T is the corresponding edge in T, otherwise e_{T} is the directed labelled leaf edge corresponding to the directed initial segment of e_{M}. Fig. 1 shows examples. 
4.  Treat T as a degenerate boundary of the open plane in which each edge occurs twice. List T's edges in CW order as viewed from a point in the plane, starting with the CW aspect of e_{T}. The first occurrence of an unlabelled edge is encoded "("; the second is encoded ")"; the first occurrence of a labelled leaf edge is encoded with the edge's label. 

Each edge of M encodes a pair of symbols, so the encoding is a string of length 2m over the alphabet ( ) [ ] , requiring 4m bits, or 4 bits/edge. Terminate an encoding (including the encoding of the empty map) with an additional unbalanced ) symbol to indicate endofencoding in a symbol stream or other circumstance where the length or end of the encoding is not apparent.
T is recovered from an encoded string as follows:
1.  Create an empty (tree) map T with a single vertex. Set the marker v to refer to this vertex.  
2.  For
each
successive
symbol
s
in
the
encoding,
 
3.  A subtree T_{S} of T is formed by the initial vertex, unlabelled edges and their endpoints. e_{T} is the first edge added to T, directed away from the initial vertex. 
The labelled leaf edges of T can be joined in pairs to form a map J such that the initial (resp. final) segment of each joined edge in J corresponds to a leaf labelled "[" (resp. "]") in T when traversing CCW the circuit formed in J by the joined edge and T_{S}. The original map M is an example of such a map J, and the only example since J is uniquely determined by its pairing of labelled edges and there is only one pairing: suppose edges e_{[a}, ... e_{]y}, ... e_{]z} occur in CCW order about T_{S} and e_{[a} may be paired with e_{]y} (resp. e_{]z}) in map J_{1} (resp. J_{2}). In J_{2}, e_{[a} is matched with e_{]z} so e_{]y} must be matched with some edge e_{[b} between e_{[a} and e_{]y}. Similar reasoning with the edge sequence e_{[a}, ... e_{[b}, ... e_{]y} in J_{1} leads to an infinite regression.
M is recovered from T by constructing the unique map J above. The spanning tree S of M is the tree corresponding to T_{S}. If e_{T} is unlabelled, e_{M} is the corresponding directed edge in M; otherwise, e_{M} is the directed joined edge in M with a directed initial segment corresponding to e_{T} in T.
Encoding and decoding times are O(m) given, e.g., the adjacency list representation of [Keeler95] or the quadedge data structure [Guibas85]. In encoding, O(m) time is taken to choose S, traverse T emitting symbols and compute labels for T using a copy of M (remove each successive nontree edge e adjacent to the unbounded region; e CCW about the unbounded region opposes e CCW about the circuit made by e and elements of S). In decoding, T is created in O(m) time and the labelled edges created in CCW order about T_{S} are joined in O(m) time as balanced parentheses.
Implicit Vertex, Edge and Face Orderings
Implicit orderings are useful when encoding auxilliary map data, e.g., a connected signed planar map (representing, e.g., a link diagram in knot theory) has a +/ sign on each edge, and may be encoded in 5 bits/edge by appending sign bits (in an implicit edge order) to the map encoding.
Examples of implicit orderings are: Vertex ordering: order map vertices by inorder traversal of the spanning tree S. Edge ordering: each symbol in the map encoding corresponds to a map edge; order map edges by first occurrence of a matching symbol within the map encoding. Face ordering: assign each map edge a direction  that of the matching "["labelled or unlabelled edge in the tree T, directed away from the origin vertex of e_{T}. Associate with each directed map edge e an ordered facepair (f_{1}, f_{2}) where e appears CCW (resp. CW) in a CCW traversal of the boundary of f_{1} (resp. f_{2}). Order map faces by first occurence in a concatenated list (in an implicit edge order) of facepairs.
Canonical Encodings
A canonical encoding of a map may be obtained by considering all possible encodings and selecting some unique representative, e.g. the first in a lexically ordered list of possible encodings.
The presented encoding scheme requires an arbitrary choice of directed root edge and spanning tree, yielding a combinatorially large number of candidate encodings. This number is reduced by making the spanning tree a function of the directed root edge, e.g. the tree obtained in a depthfirst exploration of the map starting from the root edge. For graph embeddings on the sphere there is an additional arbitrary choice of some face to serve as the outer unbounded region of the plane in the encoding (the plane defines the direction of the nontree edges in the encoding); this choice may be restricted, e.g., to the unique face where a CCW traversal of bounding edges encounters the CW aspect of the root edge. Thus the encoding for a map or spherical embedding can be uniquely determined by the choice of directed root edge, yielding 2m candidate encodings for a map with m edges.
Choices for candidate encodings may be further narrowed by considering some distinguished subset of edges, e.g. only edges adjoining faces or vertices of minimal degree, but possibilities are limited for relatively featureless maps with high symmetry. O(m^{2}) time and O(m) space are taken by considering all 2m candidate encodings.
Canonical encodings have wider application in grouping maps into equivalence classes: those described above group maps by isomorphism (isotopy within the oriented plane or sphere); other canonical encodings may group maps by, e.g., ignoring orientation and considering a map and its mirror image as equivalent.
References
[Chuang98]  Richie ChihNan Chuang & Ashim Garg & Xin He & MingYang Kao & HsuehI Lu. Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses. SpringerVerlag Lecture Notes in Computer Science 1443, pp. 118129. Document downloadable at [http://citeseer.nj.nec.com/chuang98compact.html] 
[Guibas85]  Leonidas Guibas & Jorge Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics, vol 4, no 2, April 1985, pp 74123. 
[Keeler95]  Kenneth Keeler & Jeffery Westbrook. Short Encodings of Planar Graphs and Maps. Discrete Applied Mathematics, vol 58 (1995), pp. 239252. Document downloadable at [http://citeseer.nj.nec.com/keeler95short.html] 
[Turán84]  György Turán. On the succinct representation of graphs. Discrete Applied Mathematics, vol 8 (1984), pp. 289294. 
Revision History


