VIA CANONICAL ORDERINGS

Title: VIA CANONICAL ORDERINGS

Research Question: How can we encode a planar graph using the fewest number of bits while maintaining its structure?

Methodology: The researchers proposed a method to encode a planar graph using a canonical ordering, which is a specific ordering of the vertices that maintains the graph's structure. They considered two scenarios: when the graph is triangulated (meaning it has been turned into a set of triangles) and when it is triconnected (meaning every vertex has at most three edges).

Results: They found that for a triangulated graph, they could encode it using 4 mbits, which is an improvement over the best previous bound of about 1 .53mbits. For a triconnected graph, they could use at most (2.5 + 2log 3)min {n, f} −7 bits, which is at most 2 .835mbits and smaller than the best previous bound of 3 mbits. Both of their schemes take O(n) time for encoding and decoding.

Implications: These results show that it is possible to encode a planar graph using a canonical ordering with a relatively small number of bits, even when considering the time complexity for encoding and decoding. This could have implications for data compression and graph theory, as well as for applications that involve encoding and decoding large graphs.

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