Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings

Simple item page
dc.creatorHe, Xin
dc.creatorKao, Ming-Yang
dc.creatorLu, Hsueh-I
dc.date2001-01-27
dc.date.accessioned2026-07-07T03:16:54Z
dc.date.available2026-07-07T03:16:54Z
dc.descriptionLet G be an embedded planar undirected graph that has n vertices, m edges, and f faces but has no self-loop or multiple edge. If G is triangulated, we can encode it using {4/3}m-1 bits, improving on the best previous bound of about 1.53m bits. In case exponential time is acceptable, roughly 1.08m bits have been known to suffice. If G is triconnected, we use at most (2.5+2\log{3})\min\{n,f\}-7 bits, which is at most 2.835m bits and smaller than the best previous bound of 3m bits. Both of our schemes take O(n) time for encoding and decoding.
dc.identifierhttps://arxiv.org/abs/cs/0101033
dc.identifierhttp://arxiv.org/abs/cs/0101033
dc.identifierSIAM Journal on Discrete Mathematics, 12(3):317--325, 1999
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30528
dc.subjectData Structures and Algorithms
dc.subjectGraphics
dc.subjectE.4; F.2.2
dc.titleLinear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
dc.typetext

Files

Collections

arXiv