Corelab Seminar

Alexandros Aggelopoulos (NTUA)
On aspects of layered graph drawing

Motivated from rules and directives of Air Traffic, we consider airports and direct-to routes as a Graph along with a specific geometric embedding (working terminology is "Traffic Graph"), and thus lead to aspects of Layered Graph Drawing. We present the concepts of planar decomposition and graph thickness θ(n), geometric thickness θ(n) and book thikness bt(n), explaining the inequality θ(n)<=θ(n)<=bt(n) and results in what regards their asymptotic behaviour. Discussing their application to our model, we first focus on complete Traffic Graphs, categorize them as convex and non-convex, and we determine some lower and upper bounds on the their number of layers, giving a first main result. We then set a bunch of questions and problems for further investigation..