Maximum Clique in Geometric Intersection Graphs
Date
2023-07-18
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
ORCID
Type
Thesis
Degree Level
Masters
Abstract
An intersection graph is a graph that represents some geometric objects as vertices, and joins edges
between the nodes corresponding to the items that intersect. The maximum clique in a geometric intersec-
tion graph is the largest mutually intersecting set of objects. In this thesis, the primary focus is to study
the maximum clique in various geometric intersection graphs. We develop three results motivated by the
maximum clique problem in the intersection graph of disks in the Euclidean plane. First, we improve the
time complexity of calculating the maximum clique in unit disk graphs from O(n3 log n) to O(n2.5 log n).
Second, we introduce a new technique called pair-oriented labelling. This method is used to show the NP-
hardness of finding a maximum clique in various geometric intersection graphs, acting as a way to augment
the commonly used co-2-subdivision approach. Finally, finding maximum clique in two classes of geometric
intersection graphs are proven to be NP-hard. These are the intersection graph of disks and axis-aligned
rectangles, and the outer triangle graph. The former is previously known to be NP-hard, and so this proof
represents the use of pair-oriented labelling in a problem that was otherwise considered difficult to prove
NP-hard using a co-2-subdivision approach. The outer triangle graph is a novel intersection graph, which
therefore provides new NP-hardness results for finding a maximum clique in geometric intersection graphs.
Description
Keywords
Maximum clique, Disk graph, Time complexity, NP-hardness
Citation
Degree
Master of Science (M.Sc.)
Department
Computer Science
Program
Computer Science