Download this article
 Download this article For screen
For printing
Recent Issues

Volume 17
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
Editors' interests
ISSN (electronic): 1944-4184
ISSN (print): 1944-4176
Author index
To appear
Other MSP journals
Comparing embedded graphs using average branching distance

Levent Batakci, Abigail Branson, Bryan Castillo, Candace Todd, Erin Wolf Chambers and Elizabeth Munch

Vol. 16 (2023), No. 3, 365–388

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.

topological data analysis, merge tree, embedded graph
Mathematical Subject Classification
Primary: 55N31, 62R40, 68R10, 68R12, 68T09
Received: 31 August 2020
Revised: 3 December 2021
Accepted: 21 June 2022
Published: 10 August 2023

Communicated by Kenneth S. Berenhaut
Levent Batakci
Case Western Reserve University
Hummelstown, PA
United States
Abigail Branson
Union University
Jackson, TN
United States
Bryan Castillo
Department of Mathematics
The University of Arizona
Tucson, AZ
United States
Candace Todd
Department of Statistics
The Pennsylvania State University
University Park, PA
United States
Erin Wolf Chambers
Department of Computer Science
Saint Louis University
St. Louis, MO
United States
Elizabeth Munch
Department of Computational Mathematics, Science and Engineering
Department of Mathematics
Michigan State University
East Lansing, MI
United States