Implementation of a planarity testing method using PQ-Trees
Alex William Cregten, Hannes Kristján Hannesson · 2017
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/.; Vefsiðan GTea er kynnt, þar hafa verið utfaerð tvo lagneta-profana reiknirit. Af þessum reikniritum, þa nýtir annað ser jarðýtu aðferð, a meðan hitt er skilvirkara reiknirit sem nýtir ser gagnaskipanið PQ-Tre sem var kynnt af K. S. Booth og G. S. Lueker. Þessi reiknirit eru raedd og keyrslutimar þeirra eru bornir saman. Forsenda til að keyra PQ-Traja lagneta-profana reikniritið, er að netið hafi st-tolusetningu, við raeðum utfaerslu a reikniriti sem akvarðar st-tolusetningu fyrir net, sem var kynnt af S. Even og R. E. Tarjan. Framenda lagfaeringar a GTea sem leyfa handvirka breytingu og skopun neta, og hugmyndir að viðbaetum við GTea eru einnig raeddar. Koðasafnið fyrir GTea er haegt að finna a eftirfarandi sloð: https://github.com/rostam/GTea/.