Blelloch and Farzan (2010) showed how we can represent succinctly any planar embedding of a connected planar simple graph while still supporting constant-time navigation queries, but their representation does not allow multi-edges. Other authors have shown how to represent any connected planar multigraph compactly while supporting fast navigation, but not with an arbitrary planar embedding of such a graph. In this paper we show how we can represent any given planar embedding of any connected planar (multi)graph using asymptotically four bits per edge such that later we can list the edges incident to any vertex in counter-clockwise order using constant time per edge, and determine whether two vertices are neighbours or find a vertex's degree in almost constant time.
@cite_30: 
@cite_14: Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A,B,C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n 3 vertices, and C contains no more than @math vertices. We exhibit an algorithm which finds such a partition A,B,C in O(n) time.
@cite_41: A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight, lines joining their incident vertices. Given an n-vertex embedded planar graph with @math , a straight-line embedding on a grid of size @math can be computed deterministically in @math time with @math processors. If randomization is used, the complexity is improved to @math expected time with the same optimal linear work. These algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes of the shared memory and permits an arbitrary processor to succeed in case of a write conflict.
@cite_29: We introduce and study orderly spanning trees of plane graphs. This algorithmic tool generalizes canonical orderings, which exist only for triconnected plane graphs. Although not every plane graph admits an orderly spanning tree, we provide an algorithm to compute an orderly pair for any connected planar graph G, consisting of an embedded planar graph H isomorphic to G, and an orderly spanning tree of H. We also present several applications of orderly spanning trees: (1) a new constructive proof for Schnyder's realizer theorem, (2) the first algorithm for computing an area-optimal 2-visibility drawing of a planar graph, and (3) the most compact known encoding of a planar graph with O(1)-time query support. All algorithms in this paper run in linear time.
@cite_52: We show that each plane graph of order n 2 3 has a straight line embedding on the n-2 by n-2 grid. This embedding is computable in time O(n). A nice feature of the vertex-coordinates is that they have a purely combinatorial meaning.
@cite_39: We consider the problem of coding planar graphs by binary strings. Depending on whether O(1)-time queries for adjacency and degree are supported, we present three sets of coding schemes which all take linear time for encoding and decoding. The encoding lengths are significantly shorter than the previously known results in each case.
@cite_27: 
@cite_12: Abstract An algorithm is presented which embeds any planar graph in a book of four pages. The algorithm runs in linear time.
Most of the navigable representations we have mentioned require complicated construction algorithms, generally defying a parallel implementation. It is not known how to compute a book embedding @cite_12 in parallel, which is necessary to build the representations of Jacobson and of Munro and Raman. There are also no parallel algorithms to build orderly spanning trees @cite_29 , necessary for the representation of Chiang Its predecessor @cite_39 uses instead a triangulation and a canonical ordering; for the latter there is only a CREW construction running in @math time with @math processors @cite_30 . As for the vertex separators @cite_14 required to build the representation of Blandford and of Blelloch and Farzan, Kao @cite_27 designed a linear-work, logarithmic-span algorithm for computing a cycle separator of a planar graph. However, the construction of these representations of planar embeddings decompose the input graph by repeatedly computing separators until each piece is sufficiently small. This increases the total work to @math even if this optimal parallel algorithm is used. The best linear-work parallel algorithms @cite_41 for building the realizers @cite_52 used in the construction of Barbay 's representation have @math span in the expected case but @math deterministic span.