Experiments on drawing 2-level hierarchical graphs

Abstract

This paper studies different heuristics for drawing 2-level hierarchical graphs. Especially, we compare the barycenter and the median heuristics. We show that the barycenter heuristic clearly outperforms the median heuristic, although only the latter has a proved bound for the maximum error done when two vertices are ordered. Moreover, we improve a known heuristic, called the greedy switching, by introducing the barycenter heuristic as a preprocessing phase for it.

Keywords:

• Graph drawing
• edge crossing
• hierarchical graph
• barycenter heuristic
• median heuristic
• greedy switching

C.R. Categories:

• F.2.2
• G.2.2