Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Introduction Hierarchical graphs are directed graphs with layering structures. They appear in applications where hierarchical structures are involved e.g. PERT networks and organization charts. Clustered graphs are graphs with clustering structures (see Fig. 1) which appear in many structured diagrams. A hierarchical graph is conventionally drawn with vertices of a layer on the same horizontal line, and arcs as curves monotonic in y direction. A hierarchical graph is hierarchical planar (h-planar) if it admits a drawing without edge crossings. For a clustered graph, the clustering structure is represented by a closed curve that defines a region. The region contains the drawing of all the vertices which belong to that cluster (see Fig. 1). A clustered graph is compound planar (c-planar) if it admits a drawing with no edge crossings or edge-region crossings. a b d e f g h k m n p A B C D E ROOT Figure 1: An ex