Tech Report CS-95-26

On-Line Convex Planarity Testing

Giuseppe Di Battista, Roberto Tamassia, and Luca Vismara

August 1995


An important class of planar straight-line drawings of graphs are the convex drawings, in which all faces are drawn as convex polygons. A graph is said to be convex planar if it admits a convex drawing. We consider the problem of testing convex planarity in a semi-dynamic environment, where a graph is subject to on-line insertions of vertices and edges. We present on-line algorithms for convex planarity testing with the following performance, where $n$ denotes the number of vertices of the graph: convex planarity testing and insertion of vertices take $O(1)$ worst-case time, insertion of edges takes $O(\log n)$ amortized time, and the space requirement of the data structure is $O(n)$. Furthermore, we give a new combinatorial characterization of convex planar graphs.

(complete text in pdf or gzipped postscript)