{"id":{"repo_id":"reykjavik","oai_identifier":"oai:skemman.is:1946/29618"},"canonical_url":"https://search.dev.ndltd.org/etd/reykjavik/oai:skemman.is:1946/29618","repository":{"repo_id":"reykjavik","name":"Reykjavík University","base_url":"https://skemman.is/oai/request"},"display":{"title":"Implementation of a planarity testing method using PQ-Trees","abstract":"Vefsíðan GTea er kynnt, þar hafa verið útfærð tvö lagneta-prófana reiknirit. Af þessum reikniritum, þá nýtir annað sér jarðýtu aðferð, á meðan hitt er skilvirkara reiknirit sem nýtir sér gagnaskipanið PQ-Tré sem var kynnt af K. S. Booth og G. S. Lueker. Þessi reiknirit eru rædd og keyrslutímar þeirra eru bornir saman. Forsenda til að keyra PQ-Trája lagnetaprófana reikniritið, er að netið hafi st-tölusetningu, við ræðum útfærslu á reikniriti sem ákvarðar st-tölusetningu fyrir net, sem var kynnt af S. Even og R. E. Tarjan. Framenda lagfæringar á GTea sem leyfa handvirka breytingu og sköpun neta, og hugmyndir að viðbætum við GTea eru einnig ræddar. Kóðasafnið fyrir GTea er hægt að finna á eftirfarandi slóð: https://github.com/rostam/GTea/.","abstract_html":"Vefsíðan GTea er kynnt, þar hafa verið útfærð tvö lagneta-prófana reiknirit. Af þessum reikniritum, þá nýtir annað sér jarðýtu aðferð, á meðan hitt er skilvirkara reiknirit sem nýtir sér gagnaskipanið PQ-Tré sem var kynnt af K. S. Booth og G. S. Lueker. Þessi reiknirit eru rædd og keyrslutímar þeirra eru bornir saman. Forsenda til að keyra PQ-Trája lagnetaprófana reikniritið, er að netið hafi st-tölusetningu, við ræðum útfærslu á reikniriti sem ákvarðar st-tölusetningu fyrir net, sem var kynnt af S. Even og R. E. Tarjan. Framenda lagfæringar á GTea sem leyfa handvirka breytingu og sköpun neta, og hugmyndir að viðbætum við GTea eru einnig ræddar. Kóðasafnið fyrir GTea er hægt að finna á eftirfarandi slóð: https://github.com/rostam/GTea/.","abstract_has_math":false,"creators":["Alex William Cregten 1995-","Hannes Hannesson 1995-"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Háskólinn í Reykjavík"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-02-15T16:29:17Z","date_published":"2018-02-15T16:29:17Z","updated_at":"2026-07-27T20:41:33Z","subjects":["Tölvunarfræði","Reiknirit","Computer science","Algorithms"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1946/29618","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Háskólinn í Reykjavík"]},{"key":"dc:creator","label":"Author","values":["Alex William Cregten 1995-","Hannes Hannesson 1995-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-02-15T16:29:16Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-02-15T16:29:16Z"]},{"key":"dc:date.issued","label":"Date","values":["2018-02-15T16:29:17Z"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Tölvunarfræði","Reiknirit","Computer science","Algorithms"]}]},{"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":["http://hdl.handle.net/1946/29618"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Vefsíðan GTea er kynnt, þar hafa verið útfærð tvö lagneta-prófana reiknirit. Af þessum reikniritum, þá nýtir annað sér jarðýtu aðferð, á meðan hitt er skilvirkara reiknirit sem nýtir sér gagnaskipanið PQ-Tré sem var kynnt af K. S. Booth og G. S. Lueker. Þessi reiknirit eru rædd og keyrslutímar þeirra eru bornir saman. Forsenda til að keyra PQ-Trája lagnetaprófana reikniritið, er að netið hafi st-tölusetningu, við ræðum útfærslu á reikniriti sem ákvarðar st-tölusetningu fyrir net, sem var kynnt af S. Even og R. E. Tarjan. Framenda lagfæringar á GTea sem leyfa handvirka breytingu og sköpun neta, og hugmyndir að viðbætum við GTea eru einnig ræddar. Kóðasafnið fyrir GTea er hægt að finna á eftirfarandi slóð: https://github.com/rostam/GTea/.","The website GTea is introduced where two planarity testing algorithms have been implemented. Of these two algorithms, one is a brute-force method and the other a much faster PQ-Tree method introduced by K. S. Booth and G. S. Lueker. The two algorithms are discussed and running times compared in detail. A prerequisite algorithm to the PQ-Tree method is examined and implemented, which determines an st-numbering. The algorithm was introduced by S. Even and R. E. Tarjan. Front-end additions to GTea are shown which involve the manual modification and creation of graphs. A discussion on where this project has left GTea and the next steps forward are examined. The codebase of GTea can be found at the following link: https://github.com/rostam/GTea/."]},{"key":"dc:title","label":"Title","values":["Implementation of a planarity testing method using PQ-Trees"]}]}],"canonical_facts":{"dc:contributor":["Háskólinn í Reykjavík"],"dc:creator":["Alex William Cregten 1995-","Hannes Hannesson 1995-"],"dc:date.accessioned":["2018-02-15T16:29:16Z"],"dc:date.available":["2018-02-15T16:29:16Z"],"dc:date.issued":["2018-02-15T16:29:17Z"],"dc:description.abstract":["Vefsíðan GTea er kynnt, þar hafa verið útfærð tvö lagneta-prófana reiknirit. Af þessum reikniritum, þá nýtir annað sér jarðýtu aðferð, á meðan hitt er skilvirkara reiknirit sem nýtir sér gagnaskipanið PQ-Tré sem var kynnt af K. S. Booth og G. S. Lueker. Þessi reiknirit eru rædd og keyrslutímar þeirra eru bornir saman. Forsenda til að keyra PQ-Trája lagnetaprófana reikniritið, er að netið hafi st-tölusetningu, við ræðum útfærslu á reikniriti sem ákvarðar st-tölusetningu fyrir net, sem var kynnt af S. Even og R. E. Tarjan. Framenda lagfæringar á GTea sem leyfa handvirka breytingu og sköpun neta, og hugmyndir að viðbætum við GTea eru einnig ræddar. Kóðasafnið fyrir GTea er hægt að finna á eftirfarandi slóð: https://github.com/rostam/GTea/.","The website GTea is introduced where two planarity testing algorithms have been implemented. Of these two algorithms, one is a brute-force method and the other a much faster PQ-Tree method introduced by K. S. Booth and G. S. Lueker. The two algorithms are discussed and running times compared in detail. A prerequisite algorithm to the PQ-Tree method is examined and implemented, which determines an st-numbering. The algorithm was introduced by S. Even and R. E. Tarjan. Front-end additions to GTea are shown which involve the manual modification and creation of graphs. A discussion on where this project has left GTea and the next steps forward are examined. The codebase of GTea can be found at the following link: https://github.com/rostam/GTea/."],"dc:identifier.uri":["http://hdl.handle.net/1946/29618"],"dc:language.iso":["en"],"dc:subject":["Tölvunarfræði","Reiknirit","Computer science","Algorithms"],"dc:title":["Implementation of a planarity testing method using PQ-Trees"],"dc:type":["Thesis"]},"updated_at":"2026-07-27T20:41:33Z"}