Hyperbolic Sphericity
Bachelor’s Thesis of
Lennart Großkreutz
At the Department of Informatics
Institute of Theoretical Informatics (ITI)
Reviewer: T.T.-Prof. Dr. Thomas Bläsius
Second reviewer: Dr. rer. nat. Torsten Ueckerdt
Advisor: M.Sc. Jean-Pierre von der Heydt
15/05/2024 – 16/09/2024
KIT – The Research University in the Helmholtz Association www.kit.edu
,I declare that I have developed and written the enclosed thesis completely by myself. I have not used any
other than the aids that I have mentioned. I have marked all parts of the thesis that I have included from
referenced literature, either in their original wording or paraphrasing their contents. I have followed
the by-laws to implement scientific integrity at KIT.
Karlsruhe, 16/09/2024
............................................
(Lennart Großkreutz)
,Abstract
The Euclidean sphericity of a graph 𝐺 denotes the smallest integer 𝑛 ∈ ℕ such that 𝐺 can be represented
as an intersection graph of equal-sized balls of radius 𝑟 in 𝑛-dimensional Euclidean space. Modern
research strongly suggests that extending this type of intersection graphs to hyperbolic space is of great
relevance, with applications in network science and machine learning. However, little is known about
the corresponding graph classes so far.
To establish a foundation in this new research area, we introduce the concept of hyperbolic sphericity.
This graph invariant resembles its Euclidean counterpart, with an important addition: different choices
of the parameter 𝑟 generally result in different graph classes in the hyperbolic context. We prove that
hyperbolic sphericity is bounded from above by Euclidean sphericity, if 𝑟 is chosen small. Conversely,
large choices of 𝑟 might increase hyperbolic sphericity, but by at most one. In other cases (e.g. trees),
large choices of 𝑟 can lead to a particularly low hyperbolic sphericity in comparison to the Euclidean
one.
Zusammenfassung
Die euklidische Sphärizität eines Graphen 𝐺 bezeichnet die kleinste natürliche Zahl 𝑛 ∈ ℕ, sodass 𝐺 als
Schnittgraph von Bällen mit einheitlichem Radius 𝑟 im 𝑛-dimensionalen euklidischen Raum dargestellt
werden kann. Moderne Forschung deutet darauf hin, dass solche Schnittgraphen im hyperbolischen
Raum von großer Relevanz sind, mit Anwendungen in der Netzwerkwissenschaft und dem maschinellen
Lernen. Jedoch ist bisher kaum etwas über die entsprechenden Graphklassen bekannt.
Um eine Grundlage in diesem neuen Forschungsbereich zu schaffen, führen wir das Konzept der
hyperbolischen Sphärizität ein. Diese Graphinvariante ähnelt ihrem euklidischen Gegenstück, mit einem
wichtigen Zusatz: Verschiedene Werte des Parameters 𝑟 führen im Allgemeinen zu verschieden Graph-
klassen im hyperbolischen Kontext. Wir beweisen, dass die hyperbolische Sphärizität von oben durch
die euklidische Sphärizität beschränkt ist, wenn 𝑟 klein gewählt ist. Im Gegensatz dazu können große
Werte für 𝑟 dazu führen, dass die hyperbolische Sphärizität wächst, aber höchstens um eins. In anderen
Fällen (z.B. bei Bäumen) können große Werte für 𝑟 dazu führen, dass die hyperbolische Sphärizität
besonders klein ist im Vergleich zur Euklidischen.
i
, Contents
1 Introduction 1
1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Preliminaries 5
2.1 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Euclidean Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Circles in the Euclidean Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Geodesics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.1 Distance-Preserving Functions and Isometries . . . . . . . . . . . . . . . . . . . 9
2.3.2 Geodesic Segments and Geodesics . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Hyperbolic Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.1 The Poincaré Disk Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.2 The Upper Half-Space Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.3 The Hyperboloid Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.4 Model-Independent Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.5 Hyperbolic Plane Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Unit Ball Graphs and Sphericity 23
3.1 Unit Ball Graph Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Strict UBG Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Sphericity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 Comparing Euclidean and Hyperbolic Sphericity 31
4.1 Hyperbolic Sphericity Is Well-Defined . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Euclidean UBGs as a Special Case of Hyperbolic UBGs . . . . . . . . . . . . . . . . . . 32
4.3 Computability of Hyperbolic Sphericity . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 Trees 38
5.1 Euclidean Sphericity of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Trees Are Hyperbolic UDGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2.1 Hyperbolic Tilings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6 Hyperbolic UDGs: Influence of Threshold Radius 53
6.1 Star Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.2 Relation Between Unit Disk Graphs and Planarity . . . . . . . . . . . . . . . . . . . . . 55
6.3 Great Threshold Radius Potentially Suboptimal . . . . . . . . . . . . . . . . . . . . . . . 58
6.3.1 Upper Bound for Great Threshold Radii . . . . . . . . . . . . . . . . . . . . . . 60
6.4 Open Question: Medium Threshold Radius Potentially Suboptimal . . . . . . . . . . . . 62
7 Unit Ball Graphs in Spherical Space 65
ii
Bachelor’s Thesis of
Lennart Großkreutz
At the Department of Informatics
Institute of Theoretical Informatics (ITI)
Reviewer: T.T.-Prof. Dr. Thomas Bläsius
Second reviewer: Dr. rer. nat. Torsten Ueckerdt
Advisor: M.Sc. Jean-Pierre von der Heydt
15/05/2024 – 16/09/2024
KIT – The Research University in the Helmholtz Association www.kit.edu
,I declare that I have developed and written the enclosed thesis completely by myself. I have not used any
other than the aids that I have mentioned. I have marked all parts of the thesis that I have included from
referenced literature, either in their original wording or paraphrasing their contents. I have followed
the by-laws to implement scientific integrity at KIT.
Karlsruhe, 16/09/2024
............................................
(Lennart Großkreutz)
,Abstract
The Euclidean sphericity of a graph 𝐺 denotes the smallest integer 𝑛 ∈ ℕ such that 𝐺 can be represented
as an intersection graph of equal-sized balls of radius 𝑟 in 𝑛-dimensional Euclidean space. Modern
research strongly suggests that extending this type of intersection graphs to hyperbolic space is of great
relevance, with applications in network science and machine learning. However, little is known about
the corresponding graph classes so far.
To establish a foundation in this new research area, we introduce the concept of hyperbolic sphericity.
This graph invariant resembles its Euclidean counterpart, with an important addition: different choices
of the parameter 𝑟 generally result in different graph classes in the hyperbolic context. We prove that
hyperbolic sphericity is bounded from above by Euclidean sphericity, if 𝑟 is chosen small. Conversely,
large choices of 𝑟 might increase hyperbolic sphericity, but by at most one. In other cases (e.g. trees),
large choices of 𝑟 can lead to a particularly low hyperbolic sphericity in comparison to the Euclidean
one.
Zusammenfassung
Die euklidische Sphärizität eines Graphen 𝐺 bezeichnet die kleinste natürliche Zahl 𝑛 ∈ ℕ, sodass 𝐺 als
Schnittgraph von Bällen mit einheitlichem Radius 𝑟 im 𝑛-dimensionalen euklidischen Raum dargestellt
werden kann. Moderne Forschung deutet darauf hin, dass solche Schnittgraphen im hyperbolischen
Raum von großer Relevanz sind, mit Anwendungen in der Netzwerkwissenschaft und dem maschinellen
Lernen. Jedoch ist bisher kaum etwas über die entsprechenden Graphklassen bekannt.
Um eine Grundlage in diesem neuen Forschungsbereich zu schaffen, führen wir das Konzept der
hyperbolischen Sphärizität ein. Diese Graphinvariante ähnelt ihrem euklidischen Gegenstück, mit einem
wichtigen Zusatz: Verschiedene Werte des Parameters 𝑟 führen im Allgemeinen zu verschieden Graph-
klassen im hyperbolischen Kontext. Wir beweisen, dass die hyperbolische Sphärizität von oben durch
die euklidische Sphärizität beschränkt ist, wenn 𝑟 klein gewählt ist. Im Gegensatz dazu können große
Werte für 𝑟 dazu führen, dass die hyperbolische Sphärizität wächst, aber höchstens um eins. In anderen
Fällen (z.B. bei Bäumen) können große Werte für 𝑟 dazu führen, dass die hyperbolische Sphärizität
besonders klein ist im Vergleich zur Euklidischen.
i
, Contents
1 Introduction 1
1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Preliminaries 5
2.1 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Euclidean Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Circles in the Euclidean Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Geodesics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.1 Distance-Preserving Functions and Isometries . . . . . . . . . . . . . . . . . . . 9
2.3.2 Geodesic Segments and Geodesics . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Hyperbolic Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.1 The Poincaré Disk Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.2 The Upper Half-Space Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.3 The Hyperboloid Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.4 Model-Independent Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.5 Hyperbolic Plane Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Unit Ball Graphs and Sphericity 23
3.1 Unit Ball Graph Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Strict UBG Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Sphericity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 Comparing Euclidean and Hyperbolic Sphericity 31
4.1 Hyperbolic Sphericity Is Well-Defined . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Euclidean UBGs as a Special Case of Hyperbolic UBGs . . . . . . . . . . . . . . . . . . 32
4.3 Computability of Hyperbolic Sphericity . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 Trees 38
5.1 Euclidean Sphericity of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Trees Are Hyperbolic UDGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2.1 Hyperbolic Tilings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6 Hyperbolic UDGs: Influence of Threshold Radius 53
6.1 Star Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.2 Relation Between Unit Disk Graphs and Planarity . . . . . . . . . . . . . . . . . . . . . 55
6.3 Great Threshold Radius Potentially Suboptimal . . . . . . . . . . . . . . . . . . . . . . . 58
6.3.1 Upper Bound for Great Threshold Radii . . . . . . . . . . . . . . . . . . . . . . 60
6.4 Open Question: Medium Threshold Radius Potentially Suboptimal . . . . . . . . . . . . 62
7 Unit Ball Graphs in Spherical Space 65
ii
