Tech Report CS-89-31

On-Line Planarity Testing

Giuseppe Di Battista and Roberto Tamassia

May 1989

Abstract:

The {\em on-line planarity testing} problem consists of performing the following operations on a planar graph $G$ with $n$ vertices: \begin{enumerate} \item testing if a new edge can be added to {\em G} so that the resulting graph is itself planar; \item adding vertices and edges such that planarity is preserved. \end{enumerate} We present an efficient technique for on-line planarity testing that uses $O(n)$ space and supports tests and insertions of vertices and edges in $O(\log n)$ time. The bounds for queries and vertex insertions are worst-case and the bound for edge insertions is amortized.