NDLI: The Edit Distance for Reeb Graphs of Surfaces

Content Provider	Springer Nature Link
Author	Landi, Claudia Di Fabio, Barbara
Copyright Year	2016
Abstract	Reeb graphs are structural descriptors that capture shape properties of a topological space from the perspective of a chosen function. In this work, we define a combinatorial distance for Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. The main contributions of this paper are the stability property and the optimality of this edit distance. More precisely, the stability result states that changes in the Reeb graphs, measured by the edit distance, are as small as changes in the functions, measured by the maximum norm. The optimality result states that the edit distance discriminates Reeb graphs better than any other distance for Reeb graphs of surfaces satisfying the stability property.
Ending Page	461
Page Count	39
Starting Page	423
File Format	PDF
ISSN	01795376
e-ISSN	14320444
Journal	Discrete & Computational Geometry
Issue Number	2
Volume Number	55
Language	English
Publisher	Springer US
Publisher Date	2016-01-27
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Planar graphs; geometric and topological aspects of graph theory Morse function Computational Mathematics and Numerical Analysis Natural stratification Graph edit distance Real-valued functions Combinatorics Pattern recognition, speech recognition Shape similarity
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Theoretical Computer Science Computational Theory and Mathematics Geometry and Topology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A unified approach to distance-two colouring of graphs on surfaces

Geometric graphs with no two parallel edges

Straight Line Triangle Representations

Local chromatic number of quadrangulations of surfaces

Graphs drawn with few crossings per edge

A local criterion for Tverberg graphs

Approximation algorithms via contraction decomposition

Projective plane and Möbius band obstructions

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

The Edit Distance for Reeb Graphs of Surfaces

Similar Documents

A unified approach to distance-two colouring of graphs on surfaces

Geometric graphs with no two parallel edges

Straight Line Triangle Representations

Local chromatic number of quadrangulations of surfaces

Graphs drawn with few crossings per edge

A local criterion for Tverberg graphs

Approximation algorithms via contraction decomposition

Projective plane and Möbius band obstructions

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

The Edit Distance for Reeb Graphs of Surfaces