On embedding a cycle in a plane graph (Q1011765): Difference between revisions

The problem of drawing a non-simple cycle as a non-intersecting closed curve into a planar graph drawn in the plane with the vertices represented as circles and the edges represented as thin stripes is considered. The problem is shown to have an interpretation in the \textit{clustered planarity}. A \textit{clustered graph} \(C(G,T)\) is a graph/tree pair with the vertices of \(G\) identified with the leaves of \(T\) and the clusters of vertices of \(G\) defined via shared ancestors in \(T\). A \textit{drawing of a clustered graph} is then a drawing of \(G\) in the plane that groups the clusters so that incomparable clusters do not intersect. A clustered graph is \textit{c-planar} if a drawing exists that does not have any (naturally defined) edge and edge-region crossings. The complexity of the \(c\)-planarity testing is not known and the classes for which it has been determined are mostly the so-called \(c\)-connected cluster graphs. The authors study instead a class of (potentially) highly non-connected graphs called \textit{flat}; clustered graphs of tree depth at most \(2\). Specifically, they consider the subclass of \textit{rigid clustered cycles} whose underlying graphs are cycles with prescribed sets of edges to share their pipe (stripe). They introduce transformations that preserve the \(c\)-planarity of rigid clustered cycles and based on these transformations they present an \(O(n^3)\) time algorithm to test the \(c\)-planarity of this class (\(n\) being the number of vertices of the underlying cycle). They also present a method of extracting a planar embedding in the yes case of the algorithm.