Repository logo
 

Maximum Clique in Geometric Intersection Graphs

Date

2023-07-18

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

Part Of

item.page.relation.ispartofseries

DOI

item.page.identifier.pmid

item.page.identifier.pmcid