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.