Orderly Spanning Trees: A Generalization of Canonical Orderings for Plane Graphs

Title: Orderly Spanning Trees: A Generalization of Canonical Orderings for Plane Graphs

Abstract: This research introduces and studies the concept of orderly spanning trees, a generalization of canonical orderings for plane graphs. Although not every connected plane graph admits an orderly spanning tree, an algorithm is provided to compute an orderly pair for any connected planar graph G, consisting of a plane graph H and an orderly spanning tree of H. This tool has several applications, including a new constructive proof for Schnyder's Realizer Theorem, the first area-optimal 2-visibility drawing of G, and the best known encodings of G with O(1)-time query support. All algorithms run in linear time.

Main Research Question: How can we generalize the concept of canonical orderings for plane graphs to allow for a wider range of applications?

Methodology: The study begins by introducing the concept of orderly spanning trees, which generalizes the canonical orderings for triconnected plane graphs. The algorithm computes an orderly pair for any connected planar graph G, consisting of a plane graph H and an orderly spanning tree of H.

Results: The research presents several applications of orderly spanning trees. First, a new linear-time algorithm is provided to compute a realizer for any plane triangulation, settling an open question on the dimension of planar graphs. Second, an O(n)-time algorithm is given to produce a 2-visibility drawing for any n-node simple plane graph H, with n≥3, whose area is at most (n−1)×/floorleftbig2n+1 3/floorrightbig . The drawing is shown to be worst-case optimal according to lower bounds. Lastly, the research investigates the problem of encoding a graph G into a binary string S, with the requirement that S can be decoded to reconstruct G. The study presents a linear-time algorithm for this problem, which has applications in graph drawing and encoding.

Implications: The concept of orderly spanning trees provides a more flexible tool for graph drawing and encoding than canonical orderings, as it is not restricted to triconnected plane graphs. This allows for a wider range of applications and improved performance in various graph algorithms. The research also contributes to the field by providing new algorithms and insights into the properties of planar graphs.

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