Drawing planar partitions I
Thérèse Biedl · 1998
In this paper, we study how to draw a planar partition, i.e., a planar graph with a given partition of the vertices.The goal is to obtain a drawing without crossings such that the partition is clearly visible.Previously, only the special case of bipartite graphs has been studied.Par two models of displaying the partition, we show necessary and sufficient conditions for the existence of a drawing, and how to test them in linear time.We also present linear-time algorithms to create such drawings, if possibIe.