Maximum Clique in Geometric Intersection Graphs

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.

Name thesis:degree_name

Master of Science (M.Sc.)

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Saskatchewan

Year dc:date.issued

2023

Author dc:creator

• Espenant, Jared

Advisor dc:contributor.advisor

• Mondal, Debajyoti

Committee members dc:contributor.committeemember

• McQuillan, Ian
• Keil, Mark

• Maximum clique
• Disk graph
• Time complexity
• NP-hardness

Language dc:language.iso

en

Handle dc:identifier.uri

https://hdl.handle.net/10388/14813

OAI identifier oai:identifier

oai:harvest.usask.ca:10388/14813