Incremental convex planarity testing

An important class of planar straight-line drawings of graphs are convex dr awings. in which all the faces are drawn as convex polygons. A planar graph is said to be convex planar if it admits a convex drawing. We give a new c ombinatorial characterization of convex planar graphs based on the decompos ition of a biconnected graph into its triconnected components. We then cons ider the problem of testing convex planarity in an incremental environment, where a biconnected planar graph is subject to on-line insertions of verti ces and edges. We present a data structure for the on-line incremental conv ex planarity testing problem with the following performance, where n denote s the current number of vertices of the graph: (strictly) convex planarity testing takes O(1) worst-case time, insertion of vertices takes O (log n) w orst-case time, insertion of edges takes O (log n) amortized time, and the space requirement of the data structure is O (n). (C) 2001 Academic Press.