Title: A dynamic data structure for planar graph embedding
Abstract: We present a dynamic data structure that allows for incrementally constructing a planar embedding of a planar graph with n vertices and 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. it has no self-loops and no parallel 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.