Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings

From MaRDI portal





The authors consider the problem of encoding an embedded planar undirected unlabeled graph \(G\) with \(n\) vertices, \(m\) edges, and \(f\) faces. The aim is to minimize the number of bits needed for this encoding, where both encoding and decoding of the graph have to be possible in polynomial time. For the case that the given graph \(G\) is triangulated the authors give an encoding scheme using \({3 \over 4}m -1\) bits. If \(G\) is triconnected they give an encoding that uses at most \(2.835m\) bits. Both schemes improve on the best previously known bounds and take \(O(n)\) time for encoding and decoding. For their encoding scheme for plane triangulations the authors make use of a so-called canonical ordering of the vertices, which is known to exist for every plane triangulation and which can be determined in \(O(n)\) time [see \textit{H. de Fraysseix, J. Pach}, and \textit{R. Pollack}, Combinatorica 10, No. 1, 41-51 (1990; Zbl 0728.05016)]. For the case of triconnected plane graphs they use a similar ordering of the vertices, which again is known to be computable in linear time [see \textit{G. Kant}, IEEE Computer Society Press, 101-110 (1992; Zbl 0918.68075)]. The paper is well structured and contains many references to related results. It closes with a section on open problems.











This page was built for publication: Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4699160)