dcGG, dcRNG: New Degree-Constrained Shape-Based Faithfulness Metrics

Shape-based metrics measure how faithfully a drawing D of a large graph G shows the structure of the graph by comparing the similarity between G and a proximity graph S computed from D. In this paper, we present new degree-constrained shape-based metrics by introducing new proximity graphs dcGG and dcRNG, which constrain the degree of each vertex v in the proximity graph S to be no greater than the degree of v in G. Extensive experiments demonstrate that our new degree-constrained shape-based metrics Q<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dcRNG</inf> and Q<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dcGG</inf> can more accurately measure the shape-faithfulness than the state-of-the-art degree-sensitive shape-based metrics, with on average 29.1% better metrics for highly shape-faithful layouts. Moreover, we present extensive comparison experiments of ten popular graph layouts using our new shape-based metrics Q<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dcRNG</inf> and Q<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dcGG</inf> to recommend shape-faithful layouts for large and complex graphs. Furthermore, we present a new shape-faithful graph drawing algorithm dcShFR, based on the most popular force-directed algorithm FR, to optimize the new shape-based metrics Q<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dcRNG</inf> and Q<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dcGG</inf>. Extensive experiments demonstrate that our dcShFR algorithm computes 14.5% higher shape-faithful drawings than FR on average.