A note on obstructions to clustered planarity (Q640411)

A directed graph is clustered planar if it embeds in the plane such that at each vertex the set of in-arcs occur consecutively in the local rotation. The authors give a Kuratowski-type characterization of clustered planar graphs in terms of excluded minors under a suitable order. This order includes vertex- and arc-deletion, a restriction on subdivisions designed so that clustered planarity is hereditary, and cut-inversion which reverses the direction of all arcs incident with a vertex. They begin by listing the two minimal non-clustered-planar graphs in which every vertex is either a source or a sink. They extend the result to general digraphs using expansion: splitting a vertex into two adjacent vertices so that each new vertex is either a source or a sink.