Root demotion: efficient post-processing of layered graphs to reduce dummy vertices for hierarchical graph drawing

Abstract

One of the most popular hierarchical graph drawing frameworks - the Sugiyama, Tagawa, and Toda (STT) framework - often introduces dummy vertices to the given directed acyclic graph as part of its methodology to produce the final drawing. The inclusion of dummy vertices increases the size of the input graph and consequently inflates the run time of the subsequent algorithms. Given that most graph drawing problems are NP-hard, good layering algorithms or efficient post-processing - which produces a minimal number of dummy vertices - restrain the increased run time. Many layering or layering post-processing algorithms have quadratic or cubic run time. Here we introduce Root Demotion, a linear time post-processing algorithm for the layering produced by the Longest-Path algorithm that reduces the number of dummy vertices required compared to current post-processing algorithms, consequently shortening the remaining run time of the STT framework.