This paper introduces compressed certificates for planarity, biconnectivity
and triconnectivity in planar graphs, and prove many structural properties
of certificates in planar graphs. As an application of our compressed cert
ificates, we develop efficient dynamic planar algorithms. In particular, we
consider the following three operations on a planar graph G: (i) insert an
edge if the resultant graph remains planar; (ii) delete an edge; and (iii)
test whether an edge could be added to the graph without violating planari
ty. We show how to support each of the above operations in O(n(2/3)) time,
where n is the number of vertices in the graph. The bound for tests and del
etions is worst-case, while the bound for insertions is amortized. This is
the first algorithm for this problem with sub-linear running time, and it a
ffirmatively answers a question posed in Eppstein ct al. [1992]. We use our
compressed certificates for biconnectivity and triconnectivity to maintain
the biconnected and triconnected components of a dynamic planar graph. The
time bounds are the same: O(n(2/3)) worst-case time per edge deletion, O(n
(2/3)) amortized time per edge insertion, and O(n(2/3)) worst-case time to
check whether two vertices are either biconnected or triconnected.