Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2009-005 (January 22, 2009)

Testing Planarity of Level Graphs with Intra-level Edges
by Seok-Hee Hong and Hiroshi Nagamochi

pdf File

Drawing level graphs are well studied problem in Graph Drawing. There is a rich literature on drawing level graphs including characterization, level lanarity testing, crossing minimization and planarization. However, many real world graphs have inherent hierarchies with intra-level edges. For example, visualisation of centrality in social networks produces level graphs with both inter-level and intra-level edges. In this paper, we study the problem of drawing extended level graphs, i.e., level graphs with intra-level edges. Drawing extended level graphs was addressed as one of the open problems in social network visualisation by Ulrik Brandes. The one-sided crossing minimization problem in an extended level graph is NP-hard, and several heuristics are presented with experimental results for both horizontal drawings and radial drawings. The one-sided two-layer planarization of extended level graph problem is NP-hard, and heuristics are suggested. In this paper, we present an algorithm for testing k-layer extended level planarity for both horizontal drawings and radial drawings.