Graphics Reference
In-Depth Information
Figure
.
.
Medial axes (courtesy homas Sebastian, Philip Klein and Benjamin Kimia)
Approximate Graph Matching
Approximate graph matching consists of maximizing an index of concordance be-
tween two graphs under relabeling. Many indices have been proposed. Early ap-
proachescomputed simple graph-theoretic measures andused these tocompute dis-
tance orcorrelation coe
cients. he cophenetic correlation, forexample, isaPearson
correlation between the entries of a distance matrix and the corresponding ultra-
metric distances derived from a hierarchical clustering tree. his approach implies
a matching index based on correlating ultrametric distances from two different trees
(possibly ater relabeling).
More recent approaches use other measures to derive concordance measures. he
most famous example is the Google search engine (Brin and Page
), which uses
a graph spectral measure to assess similarity. In the field of shape recognition, prox-
imity graphs have been constructed frompolygons byusingdisks similar tothose we
discussedin theprevious section. Klein etal.(
),forexample, developeda shape-
matchingprocedureusingaderivativeofthe medial axis.hemedialaxisofapolygon
is the locus of the centers of maximal circles that touch the polygon boundary more
than once. Figure
.
shows an example.
Klein et al. (
) used an edit distance measure to evaluate matching of medial
axis graphs. Edit distance is the number of elementary operations needed to trans-
form one graph into another. In the simple case, there are two editing operators:
delete an edge, and relabel an edge. By subjecting the topology of the medial axis
representations of shape to a specific edit distance measure, Klein et al. (
) were
able to characterize
D projections of
D shapes with a high degree of accuracy, re-
gardless of orientation or scale. Torsello (
) extended these methods.
Any proximity graph can be applied to the shape-recognition problem using edit
distance or measures of similarity. Gandhi (
), for example, measured the shape
of leaves by recording turning angles at small steps along their perimeters.his mea-
sure transformed a shape into a single time series. Gandhi (
)then used dynamic
time warping (Sakoe and Chiba
) to compute a distance measure between leaf
shapes.
Conclusion
5.5.4
his chapter has covered only a fraction of the visualization applications of graph
theory. Graph-theoretic visualization isarapidlydeveloping fieldbecause only inthe
last few decades have the connections between data representation and graph theory
been made explicit. Tukey and Tukey (
)anticipated the role graph theory would
play in visualization and John Tukey was especially interested in convex hulls, mini-
