Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
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.
- Constructing compact rectilinear planar layouts using canonical representation of planar graphs
- Short encodings of planar graphs and maps
- Orderly spanning trees with applications to graph encoding and graph drawing
- Space-efficient planar acyclicity constraints. A declarative pearl
- Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights
- A compact encoding of plane triangulations with efficient query supports
- Compact encodings of planar orthogonal drawings
- A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
- An Information-Theoretic Upper Bound on Planar Graphs Using Well-Orderly Maps
- A Compact Encoding of Plane Triangulations with Efficient Query Supports
- An edgebreaker-based efficient compression scheme for regular meshes
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- The computational complexity of factored graphs
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- Visibility representations of four-connected plane graphs with near optimal heights
- Schnyder woods for higher genus triangulated surfaces, with applications to encoding
- Quick encoding of plane graphs in \(\log _{2}14\) bits per edge
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)