Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
dissertation.pdf (1.34 MB)
ETD Abstract Container
Abstract Header
Hyperbolicity, injective hulls, and Helly graphs
Author Info
Guarnera, Heather M
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=kent1594058509433274
Abstract Details
Year and Degree
2020, PHD, Kent State University, College of Arts and Sciences / Department of Computer Science.
Abstract
The δ-hyperbolicity of a graph can be viewed as a measure of how close a graph is to a tree metrically; the smaller the hyperbolicity of a graph, the closer it is metrically to a tree. For every graph G there exists a unique smallest Helly graph H(G) into which G isometrically embeds. H(G) is called the injective hull of G, and the hyperbolicity of H(G) is equal to the hyperbolicity of G. Moreover, the minimum distance between a vertex in H(G) and a vertex in G is directly proportional to the hyperbolicity of G, which is a small constant in many real-world networks. Motivated by this, we identify facility location and network analysis problems that are translatable to problems in a graph’s underlying injective hull. Of particular interest for these problems is the eccentricity e(v) of a vertex v, defined as the length of the longest shortest path from v to any other vertex. We show that the injective hull H(G) of a graph G has many nice structural and metric properties that govern the hyperbolicity of G. We analyze the eccentricity function in distance-hereditary graphs (they are 1-hyperbolic) and fully characterize their centers (the set of vertices with minimum eccentricity). We describe the eccentricity terrain of a graph, that is, a topographic perspective of a graph with respect to vertex eccentricities, akin to geomorphometry. We identify terrain shapes such as hills, valleys, and plains, and discover that the length of some shapes depends only on the hyperbolicity. Additionally, we introduce a new graph parameter called the Helly-gap, a measure of a graph’s metric deviation from its injective hull, and show that many well-known graph classes have a small Helly-gap. We present a new linear time algorithm for computing all vertex eccentricities in distance-hereditary graphs. For general graphs, we present various eccentricity approximation algorithms differing in quality in run time, parameterized by the δ-hyperbolicity or in part by the Helly-gap. We then identify several graph classes that are closed under Hellification, that is, G ∈ C implies H(G) ∈ C. We show that the injective hull of several graphs from some well-known classes of graphs are impossible to compute in subexponential time and provide a polynomial time algorithm to construct the injective hull of any distance-hereditary graph.
Committee
Feodor Dragan, Ph.D. (Advisor)
Ruoming Jin, Ph.D. (Committee Member)
Gokarna Sharma, Ph.D. (Committee Member)
Artem Zvavitch, Ph.D. (Committee Member)
Jing Li, Ph.D. (Committee Member)
Pages
123 p.
Subject Headings
Computer Science
Keywords
injective hull
;
Gromov hyperbolicity
;
Helly graphs
;
vertex eccentricities
Recommended Citations
Refworks
EndNote
RIS
Mendeley
Citations
Guarnera, H. M. (2020).
Hyperbolicity, injective hulls, and Helly graphs
[Doctoral dissertation, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1594058509433274
APA Style (7th edition)
Guarnera, Heather.
Hyperbolicity, injective hulls, and Helly graphs.
2020. Kent State University, Doctoral dissertation.
OhioLINK Electronic Theses and Dissertations Center
, http://rave.ohiolink.edu/etdc/view?acc_num=kent1594058509433274.
MLA Style (8th edition)
Guarnera, Heather. "Hyperbolicity, injective hulls, and Helly graphs." Doctoral dissertation, Kent State University, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=kent1594058509433274
Chicago Manual of Style (17th edition)
Abstract Footer
Document number:
kent1594058509433274
Download Count:
361
Copyright Info
© 2020, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.