# Tech Report CS-95-26

## On-Line Convex Planarity Testing

### Abstract:

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)