A directed graph $G$ is upward planar if it admits a planar embedding such that each edge is $y$-monotone. Unlike planarity testing, upward planarity testing is NP-hard except in restricted cases, such as when the graph has the single-source property (i.e. each connected component only has one source). In this paper, we present a dynamic algorithm for maintaining a combinatorial embedding $\mathcal{E}(G)$ of a single-source upward planar graph subject to edge deletions, edge contractions, edge insertions upwards across a face, and single-source-preserving vertex splits through specified corners. We furthermore support changes to the embedding $\mathcal{E}(G)$ on the form of subgraph flips that mirror or slide the placement of a subgraph that is connected to the rest of the graph via at most two vertices. All update operations are supported as long as the graph remains upward planar, and all queries are supported as long as the graph remains single-source. Updates that violate upward planarity are identified as such and rejected by our update algorithm. We dynamically maintain a linear-size data structure on $G$ which supports incidence queries between a vertex and a face, and upward-linkability of vertex pairs. If a pair of vertices are not upwards-linkable, we facilitate one-flip-linkable queries that point to a subgraph flip that makes them linkable, if any such flip exists. We support all updates and queries in $O(\log^2 n)$ time.

翻译：定向图形 $G$ 是向上平方图 如果它承认一个单源平面嵌入的平面图, 每个边缘都是 $ 美元 。 与平面测试不同的是, 向上平面测试是 NP- 硬的, 但有限制的情况除外, 比如, 图形有单一源属性( 即每个连接的部件只有一个源 ) 。 在本文中, 我们提出了一个动态算法, 用于维持一个组合嵌入 $\ mathcal{E}( G) 。 所有更新操作都得到支持, 只要该图仍然是向上平面的删除、 边缘收缩、 向上插入, 以及 单源保存的向上和 单源的顶端。 我们还支持在子图上嵌入 $\ mathcal{E} (G) 格式上嵌入的 $\ g$, 以子图的形式显示一个可向上递增缩动的值 。