Clustered planarity

In graph drawing, a clustered planar graph is a graph together with a hierarchical clustering on its vertices, such that the graph drawn together with a collection of simple closed curves surrounding each cluster, so that there are no crossings between graph edges or clusters.[1]

A clustered planar drawing

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.[1] 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.[2]

References
  1. Cortese, Pier Francesco; Di Battista, Giuseppe (2005), "Clustered planarity", Proc. 21st Symp. Computational Geometry (SCG'05), New York: ACM, pp. 32–34, doi:10.1145/1064092.1064093, MR 2460345. A brief survey paper associated with an invited talk at SCG.
  2. Fulek, Radoslav; Tóth, Csaba D. (2020), "Atomic embeddability, clustered planarity, and thickenability", To appear in Proc. 31st ACM-SIAM Symposium on Discrete Algorithms, arXiv:1907.13086
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.