On the succinct representation of graphs
Let \({\mathcal G}_ be\) a class of (labeled or unlabeled) graphs and \({\mathcal G}_ n\) be the class of graphs in \({\mathcal G}\) having n vertices. The problem discussed is the following: find a representation (or encoding) of graphs in \({\mathcal G}\) which is succinct (i.e. the length of the encoding of \(G\in {\mathcal G}_ n\) is not too large compared with the lower bound \(\log_ 2| {\mathcal G}_ n|)\) and efficiently (e.g. polynomial time) computable. The paper considers the case of planar graphs. An encoding using at most 12n bits is given for the unlabeled case and (improving a result of \textit{A. Itai} and \textit{M. Rodeh} [Acta Inf. 17, 215-219 (1982; Zbl 0471.68042)]), an asymptotically optimal encoding using \(n\lceil \log_ 2n\rceil +12n\) bits is given for the labeled case.
- A note on succinct representations of graphs
- Succinct representations of graphs
- Succinct Representations of Arbitrary Graphs
- Succinct representations of separable graphs
- Succinct representation of labeled graphs
- Succinct Representation of Labeled Graphs
- scientific article; zbMATH DE number 219271
- Succinct encoding of arbitrary graphs
- The complexity of searching succinctly represented graphs
- scientific article; zbMATH DE number 4110112
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- scientific article; zbMATH DE number 3685495 (Why is no real title available?)
- scientific article; zbMATH DE number 3551893 (Why is no real title available?)
- scientific article; zbMATH DE number 3419161 (Why is no real title available?)
- Representation of graphs
- Sur la rationalite de certaines séries generatrices
- The complexity of computing the permanent
- A clique-difference encoding scheme for labelled \(k\)-path graphs
- Simple planar graph partition into three forests
- Graph compression by BFS
- Short encodings of planar graphs and maps
- Navigating planar topologies in near-optimal space and time
- Succinct representation of general unlabeled graphs
- Succinct representation of labeled graphs
- Planar graphs, via well-orderly maps and trees
- Succinct encodings for families of interval graphs
- Succinct encoding of binary strings representing triangulations
- Space-efficient planar acyclicity constraints. A declarative pearl
- Bounding the number of reduced trees, cographs, and series-parallel graphs by compression
- Linearity is strictly more powerful than contiguity for encoding graphs
- Bounding the number of reduced trees, cographs, and series-parallel graphs by compression
- Asymptotic enumeration and limit laws of planar graphs
- Linearity is strictly more powerful than contiguity for encoding graphs
- Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
- Succinct Representations of Arbitrary Graphs
- Succinct representations of separable graphs
- scientific article; zbMATH DE number 4035881 (Why is no real title available?)
- Succinct encoding of arbitrary graphs
- (Nearly-)tight bounds on the contiguity and linearity of cographs
- Short Encodings of Evolving Structures
- A compact encoding of plane triangulations with efficient query supports
- scientific article; zbMATH DE number 1962839 (Why is no real title available?)
- scientific article; zbMATH DE number 2032369 (Why is no real title available?)
- A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
- The saga of minimum spanning trees
- scientific article; zbMATH DE number 219271 (Why is no real title available?)
- Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
- Compact navigation and distance oracles for graphs with small treewidth
- A note on succinct representations of graphs
- A Census of Plane Graphs with Polyline Edges
- Succinct Representation of Labeled Graphs
- Succinct Encodings of Graph Isomorphism
- A Compact Encoding of Plane Triangulations with Efficient Query Supports
- Efficient local representations of graphs
- Representing graphs implicitly using almost optimal space
- An edgebreaker-based efficient compression scheme for regular meshes
- Compact representations of spatial hierarchical structures with support for topological queries
- Implementing the topological model succinctly
- Dynamic compact planar embeddings
- Succinct planar encoding with minor operations
- The widths of strict outerconfluent graphs
- Compact representation of graphs of small clique-width
- Columnar order in random packings of 2 2 squares on the square lattice
- Finite presentation of homogeneous graphs, posets and Ramsey classes
- Schnyder woods for higher genus triangulated surfaces, with applications to encoding
- Trading uninitialized space for time
- Succinct representations of planar maps
- Quick encoding of plane graphs in \(\log _{2}14\) bits per edge
This page was built for publication: On the succinct representation of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800734)
