Root demotion: efficient post-processing of layered graphs to reduce dummy vertices for hierarchical graph drawing
Daniel Summer Magruder and Stefan Bonn
Vol. 21, no. 6, pp. 1027-1038, 2017. Concise paper.
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.
Submitted: March 2017.
Reviewed: June 2017.
Revised: July 2017.
Accepted: August 2017.
Final: September 2017.
Published: October 2017.
Communicated by Giuseppe Liotta
article (PDF)