Convex drawings of intersecting families of simple closed curves.
Bette Bultena, Branko Grünbaum, Frank Ruskey · 1999
A FISC or family of intersecting simple closed curves is a collection of simple closed curves in the plane with the properties that there is some open region common to the interiors of all the curves, and that every two curves intersect in nitely many points. Let F be a FISC. Intersections of the curves represent the vertices of a plane graph, G(F), whose edges are the curve arcs between vertices. The directed dual of G(F), denoted ~ D(F), is the dual graph of G(F), but with edges oriented to indicate inclusion in fewer interiors of the curves. A convex drawing of G(F) is one in which every curve is convex. The graph G(F) has a convex drawing if there is some FISC C whose curves are all convex and where F can be transformed into C by a continuous transformation of the plane. We prove that G(F) has a convex drawing if and only if ~ D(F) contains only one source and only one sink. This means that we can determine in O(v) time, where v is the number of vertices in G(F), whether F admits a convex drawing in the plane.