  Shape-based metrics measure how faithfully a drawing D represents the
structure of a graph G, using the proximity graph S of D. While some limited
graph classes admit proximity drawings (i.e., optimally shape-faithful
drawings, where S = G), algorithms for shape-faithful drawings of general
graphs have not been investigated. In this paper, we present the first study
for shape-faithful drawings of general graphs. First, we conduct extensive
comparison experiments for popular graph layouts using the shape-based metrics,
and examine the properties of highly shape-faithful drawings. Then, we present
ShFR and ShSM, algorithms for shape-faithful drawings based on force-directed
and stress-based algorithms, by introducing new proximity forces/stress.
Experiments show that ShFR and ShSM obtain significant improvement over FR
(Fruchterman-Reingold) and SM (Stress Majorization), on average 12% and 35%
respectively, on shape-based metrics.
