Matchings in Geometric Graphs

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Biniaz, Ahmad

Date: 

2017

Abstract: 

A geometric graph is a graph whose vertex set is a set of points in the plane and whose edge set contains straight-line segments. A matching in a graph is a subset of edges of the graph with no shared vertices. A matching is called perfect if it matches all the vertices of the underling graph. A geometric matching is a matching in a geometric graph. In this thesis, we study matching problems in various geometric graphs. Among the family of geometric graphs we look at complete graphs, complete bipartite graphs, complete multipartite graphs, Delaunay graphs, Gabriel graphs, and Θ-graphs. The classical matching problem is to find a matching of maximum size in a given graph. We study this problem as well as some of its variants on geometric graphs. The bottleneck matching problem is to find a maximum matching that minimizes the length of the longest edge. The plane matching problem is to find a maximum matching so that the edges in the matching are pairwise non-crossing. A geometric matching is strong with respect to a given shape S if we can assign to each edge in the matching a scaled version of S such that the shapes representing the edges are pairwise disjoint. The strong matching problem is to find the maximum strong matching with respect to a given shape. The matching packing problem is to pack as many edge-disjoint perfect matchings as possible into a geometric graph. We study these problems and establish lower and upper bounds on the size of different kinds of matchings in various geometric graphs. We also present algorithms for computing such matchings. Some of the presented bounds are tight, while the others need to be sharpened.

Subject: 

Computer Science

Language: 

English

Publisher: 

Carleton University

Contributor: 

co-author: 
Subhas Nandy
publisher: 
Elsevier Elsevier
co-author: 
Paz Carmi

Thesis Degree Name: 

Doctor of Philosophy: 
Ph.D.

Thesis Degree Level: 

Doctoral

Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).