Combinatorial Characterization of Upward Planarity
- PDF / 816,055 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 221 Views
Combinatorial Characterization of Upward Planarity Xuexing Lu1,2
· Yu Ye1,2
Received: 27 October 2017 / Revised: 7 December 2018 / Accepted: 10 December 2018 © School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract We give a combinatorial characterization of upward planar graphs in terms of upward planar orders, which are special linear extensions of edge posets. Keywords Upward planar graph · Planar st graph · Upward planar order Mathematics Subject Classification 05C10 · 06A99
1 Introduction A planar drawing of a directed graph is upward if all edges increase monotonically in the vertical direction (or other fixed direction). A directed graph is called upward planar if it admits an upward planar drawing; see Fig. 1 for example. Clearly, an upward planar graph is necessarily acyclic. A directed graph together with an upward planar drawing is called an upward plane graph. They are commonly used to represent hierarchical structures, such as PERT networks, Hasse diagrams, family trees, etc., and have been extensively studied in the fields of graph theory, graph drawing algorithms, and ordered set theory (see, e.g., [5] for a review). A first simple characterization of upward planarity was given independently by Di Battista and Tamassia [3] and Kelly [8]. They characterized upward planar graphs as spanning subgraphs of planar st graphs, as shown in Fig. 2, where a planar st graph is a directed planar graph with exactly one source s, exactly one sink t, and a distinguished edge e connecting s, t.
B
Xuexing Lu [email protected] Yu Ye [email protected]
1
School of Mathematical Sciences, University of Science and Technology of China, Hefei, China
2
Wu Wen-Tsun Key Laboratory of Mathematics, Chinese Academy of Sciences, Hefei, China
123
X. Lu, Y. Ye
Fig. 1 An upward planar graph
t
e
s Fig. 2 A planar st graph with the graph in Fig. 1 as spanning subgraph
Another fundamental characterization of upward planar graphs was given in [1,2] by means of bimodal planar drawings [5] and consistent assignments of sources and sinks to faces. Aware of these elegant and important combinatorial characterizations, in this paper, we will study upward planarity in a different approach. The notion of a processive plane graph (called a PPG for short, see Definition 2.1) was introduced in [6] as a graphical tool for tensor calculus in semi-groupal categories. It turns out that a PPG is essentially equivalent to an upward plane st graph, as shown in Fig. 3. The notion of a progressive plane graph, with that of a PPG as a special case, was introduced by Joyal and Street in [7] as a graphical tool for tensor calculus in monoidal categories. Similar to the above characterization of Di Battista and Tamassia [3] and Kelly [8], any progressive plane graph can be extended (in a non-unique way) to a PPG, as shown in Fig. 4. It is clear that a progressive plane graph is essentially an upward planar graph (possibly with isolated vertices).
Data Loading...
