Drawing Directed Graphs


S. Hong and H. Nagamochi, "Convex Drawings of Hierarchical Planar Graphs and Clustered Planar Graphs", Journal of Discrete Algorithm, Elsevier, 8(3), pp. 282-295, 2010.

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.
We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43-69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a "fully convex drawing," a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.



C. Bachmaier, H. Buchner, M. Forster and S. Hong, "Crossing minimization in Extended Level Drawings of Graphs", Discrete Applied Mathematics, 158(3), pp. 159-179, 2010, Elsevier.

The most popular method of drawing directed graphs is to place vertices on a set of horizontal or concentric levels, known as level drawings. Level drawings are well studied in Graph Drawing due to their strong application for the visualization of hierarchy in graphs. There are two drawing conventions: Horizontal drawings use a set of parallel lines and radial drawings use a set of concentric circles. In level drawings, edges are only allowed between vertices on different levels. However, many real world graphs exhibit hierarchies with edges between vertices on the same level. In this paper, we initiate the new problem of extended level drawings of graphs, which was addressed as one of the open problems in social network visualization, in particular, displaying centrality values of actors. More specifically, we study minimizing the number of edge crossings in extended level drawings of graphs. The main problem can be formulated as the extended one-sided crossing minimization problem between two adjacent levels, as it is folklore with the one-sided crossing minimization problem in horizontal drawings.
We first show that the extended one-sided crossing minimization problem is NP-hard for both horizontal and radial drawings, and then present efficient heuristics for minimizing edge crossings in extended level drawings. Our extensive experimental results show that our new methods reduce up to 30% of edge crossings.



S. Hong, N. Nikolov, and A. Tarassov, "A 2.5D Hierarchical Drawing of Directed Graphs", Journal of Graph Algorithms and Applications, Vol. 11, no. 2, pp. 371-396, 2007.

We introduce a new graph drawing convention for 2.5D hierarchical drawings of directed graphs. The vertex set is partitioned both into layers of vertices drawn in parallel planes and into k >= 2 subsets, called walls, and also drawn in parallel planes. The planes of the walls are perpen- dicular to the planes of the layers. We present a method for computing such layouts and introduce five alternative algorithms for partitioning the vertex set into walls which correspond to different aesthetic requirements. We evaluate our method with an extensive computational study.