dc.contributor.author | St Denis, Michael | |
dc.date.accessioned | 2023-04-28T14:01:48Z | |
dc.date.available | 2023-04-28T14:01:48Z | |
dc.date.issued | 2023-04-28 | |
dc.identifier.uri | http://hdl.handle.net/10222/82548 | |
dc.description.abstract | This thesis presents a way to compactly represent dynamic connected planar embeddings,
which may contain self loops and multi-edges, in 4m + o(m) bits, to support
basic navigation in O(lg n) time and edge and vertex insertion and deletion in
O(lg^(1+ϵ) n) time, where n and m are respectively the number of vertices and edges
currently in the graph and ϵ is an arbitrary positive constant. Previous works on
dynamic succinct planar graphs either do not provide a full set of update operations
or are restricted to triangulations where the outer face must be a simple polygon and
all inner faces must be triangles. To the best of our knowledge, this thesis presents
the first representation of dynamic compact connected planar embeddings that supports
a full set of dynamic operations without restrictions on the sizes or shapes of
the faces. | en_US |
dc.language.iso | en | en_US |
dc.subject | planar embedding | en_US |
dc.subject | dynamic planar embedding | en_US |
dc.subject | dynamic compact data structures | en_US |
dc.title | Dynamic Compact Planar Embeddings | en_US |
dc.date.defence | 2023-04-26 | |
dc.contributor.department | Faculty of Computer Science | en_US |
dc.contributor.degree | Master of Computer Science | en_US |
dc.contributor.external-examiner | n/a | en_US |
dc.contributor.graduate-coordinator | Michael McAllister | en_US |
dc.contributor.thesis-reader | Travis Gagie | en_US |
dc.contributor.thesis-reader | Nauzer Kalyaniwalla | en_US |
dc.contributor.thesis-supervisor | Meng He | en_US |
dc.contributor.ethics-approval | Not Applicable | en_US |
dc.contributor.manuscripts | Not Applicable | en_US |
dc.contributor.copyright-release | Not Applicable | en_US |