Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses

Title: Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses

Research Question: How can we create efficient encoding schemes for planar graphs that take into account the level of query support and the structure of the encoded graphs?

Methodology: The researchers proposed three sets of coding schemes for a planar graph G. These schemes employ new properties of canonical orderings for planar graphs and new techniques for processing strings of multiple types of parentheses. The bit counts for these schemes depend on the level of query support and the structure of the encoded graphs.

Results: The researchers found that their schemes take O(m+n) time for encoding and decoding. They also provided bit counts for various scenarios, such as support for adjacency queries, reconstruction of the graph from the code, and the presence of multiple edges or self-loops. They showed that their schemes can achieve bit counts significantly lower than previous best bounds in many cases.

Implications: These new encoding schemes for planar graphs have several implications. They provide more efficient ways to encode and decode planar graphs, which can be beneficial in various applications such as graph theory, computer science, and network analysis. The schemes also offer insights into the possibilities of achieving information-theoretic tight bounds for encoding other graph families.

Link to Article: https://arxiv.org/abs/0102005v2 Authors: arXiv ID: 0102005v2