ONLINE PLANAR GRAPH EMBEDDING

We present a dynamic data structure for the incremental construction o f a planar embedding of a planar graph. The data structure supports th e following operations: (i) testing if a new edge can be added to the embedding without introducing crossing; and (ii) adding vertices and e dges. The: time complexity of each operation is O(log n) (amortized fo r edge insertion), and the memory space and preprocessing time are O(n ), where n is the current number of vertices of the graph. (C) 1996 Ac ademic Press, Inc.