graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, car ...

, a clustered planar graph is a graph together with a

hierarchical clustering In data mining and statistics, hierarchical clustering (also called hierarchical cluster analysis or HCA) is a method of cluster analysis that seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into tw ...

on its vertices, such that the graph drawn together with a collection of

simple closed curve In topology, the Jordan curve theorem asserts that every ''Jordan curve'' (a plane simple closed curve) divides the plane into an "interior" region bounded by the curve and an " exterior" region containing all of the nearby and far away exterior ...

s surrounding each cluster, so that there are no crossings between graph edges or clusters.. A brief survey paper associated with an invited talk at SCG. The clustering can be described combinatorially by a collection of subsets of the vertices such that, for each two subsets, either both are disjoint or one is contained in the other. It is not required that the clustering be maximal nor that every vertex belong to a cluster. In a clustered planar drawing, no two edges may cross each other (that is, the graph must be planar), no two of the curves representing clusters may cross each other, an edge may cross a cluster boundary only if it connects a vertex inside the cluster to a vertex outside the cluster, and when an edge and cluster boundary cross they may cross only once. After much past work on the problem, a polynomial-time algorithm testing clustered planarity was found in 2019 by Radoslav Fulek and Csaba Tóth.

References

{{reflist Graph drawing