{"id":{"repo_id":"sask","oai_identifier":"oai:harvest.usask.ca:10388/14813"},"canonical_url":"https://search.dev.ndltd.org/etd/sask/oai:harvest.usask.ca:10388/14813","repository":{"repo_id":"sask","name":"University of Saskatchewan","base_url":"https://harvest.usask.ca/server/oai/request"},"display":{"title":"Maximum Clique in Geometric Intersection Graphs","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Espenant, Jared"],"institution":"University of Saskatchewan","degree_name":"Master of Science (M.Sc.)","degree_level":"Masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Mondal, Debajyoti"],"committee_chairs":[],"committee_members":["McQuillan, Ian","Keil, Mark"],"year":2023,"date_issued":"2023-07-18","date_published":"2023-07-18","updated_at":"2026-07-24T04:26:52Z","subjects":["Maximum clique","Disk graph","Time complexity","NP-hardness"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/10388/14813","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Mondal, Debajyoti"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["McQuillan, Ian","Keil, Mark"]},{"key":"dc:creator","label":"Author","values":["Espenant, Jared"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2023-07-18T18:54:54Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2023-07-18T18:54:54Z"]},{"key":"dc:date.issued","label":"Date","values":["2023-07-18"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (M.Sc.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Saskatchewan"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Maximum clique","Disk graph","Time complexity","NP-hardness"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10388/14813"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Maximum Clique in Geometric Intersection Graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Mondal, Debajyoti"],"dc:contributor.committeemember":["McQuillan, Ian","Keil, Mark"],"dc:creator":["Espenant, Jared"],"dc:date.accessioned":["2023-07-18T18:54:54Z"],"dc:date.available":["2023-07-18T18:54:54Z"],"dc:date.issued":["2023-07-18"],"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","Disk graph","Time complexity","NP-hardness"],"dc:title":["Maximum Clique in Geometric Intersection Graphs"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science (M.Sc.)"],"thesis:institution_name":["University of Saskatchewan"]},"updated_at":"2026-07-24T04:26:52Z"}