Matchings in Geometric Graphs
Ahmad Biniaz · 2017
contents 5.3.2 2 5 -approximation algorithm for connected unit disk graphs 86 5.4 Approximating Bottleneck Plane Perfect Matching 88 5.4.1 First Approximation Algorithm 89 5.4.2 Second Approximation Algorithm 93 5.5 Conclusions 101 6 bottleneck plane matchings in bipartite graphs 103 6.1 Introduction 103 6.2 Points in Convex Position 103 6.2.1 Points on Circle 104 6.3 Blue Points on Straight Line 107 6.3.1 First algorithm 107 6.3.2Second algorithm 108 7 plane matchings in complete multipartite graphs 111 7.1 Introduction 111 7.2 Balanced Cut Theorem 115 7.3 Plane Colored Matching Algorithm 120 7.3.1 Maximum Matching 121 8 packing matchings into a point set 125 8.1 Introduction 125 8.2 Preliminaries 128 8.3 Packing Plane Matchings into Point Sets 130 8.3.1 Points in Convex Position 130 8.3.2Points in Wheel Configurations 131 8.3.3Points in General Position 134 8.3.4Non-crossing Plane Matchings 140 8.4 Matching Removal Persistency 141 8.5 Conclusions 144 P R E FA C EThis thesis is in "integrated article format" in which each chapter is based on published papers, conference proceedings, or papers awaiting publication.• Chapter 2 considers the matching problems in Gabriel graphs.This chapter is a combination of results that have been published in the journal of Theoretical Computer Science [9] and results that have been presented in the 32nd European Workshop on Computational Geometry (EuroCG'16) [5].• Chapter 3 considers matching problems in triangular-distance Delaunay graphs.This chapter presents the results that have been published in the journal of Computational Geometry: Theory and Applications [7].A preliminary version of these results have been published in the proceedings of the First International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2015) [8].• Chapter 4 considers the strong matching problem.This chapter is based on the results that have been accepted for publication in the journal of Computational Geometry: Theory and Applications, special issue in memoriam: Ferran Hurtado [4].• Chapter 5 considers the non-crossing bottleneck matching problem in a point set.The results of this chapter have been published in the journal of Computational Geometry: Theory and Applications [1].• Chapter 6 considers the non-crossing bottleneck matching problem in bipartite geometric graphs.The results of this chapter have appeared in the proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014) [6].• Chapter 7 considers the non-crossing maximum matching problem in complete multipartite geometric graphs.The results of this chapter have been published in the proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015) [3].• Chapter 8 considers the problem of packing edge-disjoint perfect matchings in to a complete geometric graph.The results of this chapter have been published in the journal of Discrete Mathematics & Theoretical Computer Science [2].