Maximum Clique in Geometric Intersection Graphs
| dc.contributor.advisor | Mondal, Debajyoti | |
| dc.contributor.committeeMember | McQuillan, Ian | |
| dc.contributor.committeeMember | Keil, Mark | |
| dc.creator | Espenant, Jared | |
| dc.date.accessioned | 2023-07-18T18:54:54Z | |
| dc.date.available | 2023-07-18T18:54:54Z | |
| dc.date.copyright | 2023 | |
| dc.date.created | 2023-07 | |
| dc.date.issued | 2023-07-18 | |
| dc.date.submitted | July 2023 | |
| dc.date.updated | 2023-07-18T18:54:55Z | |
| dc.description.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. | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | https://hdl.handle.net/10388/14813 | |
| dc.language.iso | en | |
| dc.subject | Maximum clique | |
| dc.subject | Disk graph | |
| dc.subject | Time complexity | |
| dc.subject | NP-hardness | |
| dc.title | Maximum Clique in Geometric Intersection Graphs | |
| dc.type | Thesis | |
| dc.type.material | text | |
| thesis.degree.department | Computer Science | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | University of Saskatchewan | |
| thesis.degree.level | Masters | |
| thesis.degree.name | Master of Science (M.Sc.) |