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

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

Abstract: This research introduces and studies the concept of orderly spanning trees, a generalization of canonical orderings for planar graphs. The main contributions include:

1. An algorithm to compute an orderly pair (HofG, T) for any connected planar graph G, where HofG is a plane graph and T is an orderly spanning tree of H. 2. A new constructive proof for Schnyder's Realizer Theorem, which constructs a planar embedding of a graph using an orderly spanning tree. 3. An algorithm to produce a 2-visibility drawing for any connected planar graph H, with an area that is at most (n-1)×/floorleftbig2n+1 3/floorrightbig . This drawing is shown to be area-optimal. 4. An algorithm to encode a graph into a binary string with efficient query support.

These results provide new tools and insights for graph drawing and encoding, with implications for various fields such as computer science, mathematics, and visualization.

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