On combinatorial characterization of planar $st$ graphs.

The notion of a planar $st$ graph (also known as e-bipolar planar graph) is essentially equivalent to that of a progressive plane graph, which was introduced by Joyal and Street in the theory of graphical calculus for tensor categories. Fraysseix and Mendez have shown a bijection between equivalence classes of planar $st$ embedings of a directed graph $G$ and the conjugate orders of the edge poset of $G$. In this paper, we reformulate Fraysseix-Mendez's result in term of progressive graphs and planar orders and give a totally combinatorial proof in the perspective of graphical calculus. Our proof also provides a practical method to calculate the planar orders of progressive plane graphs. Moreover, we prove that any boxed planar embedding of a progressive graph is equivalent to a progressive plane graph, which is a reformulation of a result of Battista-Tamassia and Kelly.