Orderly Pair of Connected Planar Graphs

Title: Orderly Pair of Connected Planar Graphs

Abstract: This research introduces the concept of an orderly pair for connected planar graphs, extending the concept of canonical ordering to planar graphs not required to be triconnected. The study presents a linear-time algorithm that obtains an orderly pair (H, T) of a connected planar graph G, where H is a planar embedding of G, and T is an orderly spanning tree of H. The technique of orderly spanning trees is applied to achieve the best known encoding of G with query support and the first area-optimal 2-visibility drawing of G.

Main Research Question: How can we extend the concept of canonical ordering to connected planar graphs not required to be triconnected, and what are the implications for graph encoding and graph drawing?

Methodology: The study proposes an orderly pair of connected planar graphs, extending the concept of canonical ordering. A linear-time algorithm is developed to obtain an orderly pair (H, T) of a connected planar graph G, where H is a planar embedding of G, and T is an orderly spanning tree of H.

Results: The research presents the orderly pair of connected planar graphs and an orderly spanning tree. The technique of orderly spanning trees is applied to achieve the best known encoding of G with query support and the first area-optimal 2-visibility drawing of G.

Implications: The orderly pair of connected planar graphs and the orderly spanning tree technique have implications for graph encoding and graph drawing. The best known encoding of G with query support and the first area-optimal 2-visibility drawing of G are achieved, demonstrating the effectiveness of the proposed method.

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