Combinatorial characterization of upward planarity

Xuexing Lu, Yu Ye

Published 2016-08-25Version 1

For any acyclic directed graph $G$, we introduce two notions: one is called an upward planar order on $G$ which is a linear extension of the edge poset of $G$ with some constraints, the other is called a canonical progressive planar extension (CPP extension for short) of $G$ which is an embedding of $G$ into a progressive planar graph with some constraints. Based on new characterizations of progressive planar graphs, we show that there is a natural bijection between the set of upward planar orders of $G$ and the set of CPP extensions of $G$. Finally we justify the combinatorial definition that an upward planar graph is an acyclic directed graph with an upward planar order.