Multilayer Drawings of Clustered Graphs

Abstract

The cluster adjacency graph of a flat clustered graph C(G,T) is the graph A whose vertices are the clusters in T and whose edges connect clusters containing vertices that are adjacent in G. A multilayer drawing of a clustered graph C consists of a straight-line c-planar drawing of C in which the clusters are drawn as convex regions and of a straight-line planar drawing of A such that each vertex a ∈ A is drawn in the cluster corresponding to a and such that no edge (a₁,a₂) ∈ A intersects any cluster different from a₁ and a₂. In this paper, we show that every c-planar flat clustered graph admits a multilayer drawing.