Graphs drawn in the plane are ubiquitous, arising from data sets through a variety of
methods ranging from GIS analysis to image classification to shape analysis. A
fundamental problem in this type of data is comparison: given a set of such graphs,
can we rank how similar they are in such a way that we capture their geometric
“shape” in the plane?
We explore a method to compare two such embedded graphs, via a simplified
combinatorial representation called a
tail-less merge tree which encodes the
structure based on a fixed direction. First, we examine the properties of a
distance designed to compare merge trees called the
branching distance,
and show that the distance as defined in previous work fails to satisfy some
of the requirements of a metric. We incorporate this into a new distance
function called
average branching distance to compare graphs by looking at the
branching distance for merge trees defined over many directions. Despite
the theoretical issues, we show that the definition is still quite useful in
practice by using our open-source code to cluster data sets of embedded
graphs.
PDF Access Denied
We have not been able to recognize your IP address
3.94.202.151
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our
journal-recommendation form.
Or, visit our
subscription page
for instructions on purchasing a subscription.