Tech Report CS-89-28

Dynamic Planar Graph Embedding

Roberto Tamassia

April 1989

Abstract:

We present a dynamic data structure that allows for incrementally constructing a planar embedding of a planar graph with {\em n} vertices and {\em m} edges. The data structure supports the following operations: (1) testing if a new edge can be added to the embedding without introducing crossings; (2) adding and removing vertices and edges. In each case the time complexity is $O(\log m)$. The space used and the preprocessing time are $O(m)$. If the graph is simple (i.e., has no self-loops and no multiple edges), the above bounds become $O(\log n)$ and $O(n)$, respectively. This work finds applications in circuit layout, graphics, motion planning, and computer-aided design.

(complete text in pdf)