Efficient Encoding of Planar Graphs

Title: Efficient Encoding of Planar Graphs

Research Question: How can we efficiently encode planar graphs with different levels of query support?

Methodology: The researchers proposed three sets of coding schemes for a given planar graph G. These schemes utilize new properties of canonical orderings and multiple parentheses techniques to encode and decode the graph in O(m+n) time. 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 different levels of query support, including adjacency queries, degree queries, and reconstructing the graph from its code. The results showed that their schemes can achieve bit counts significantly lower than previous bounds for certain planar graphs.

Implications: The efficient encoding of planar graphs has practical applications in various fields such as computer science, mathematics, and network analysis. The proposed coding schemes can be used to store and manipulate large graphs in a compact and efficient manner. Additionally, the new properties and techniques used in the research can potentially be applied to other graph encoding problems.

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