Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs

A directed graph G is upward planar if it admits a planar embedding where 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 has one source). In this paper, we present a dynamic data structure for maintaining an upward combinatorial embedding →E (G) of a single-source upward planar graph subject to edge deletions, edge contractions, directed edge insertions across a face, and single-source-preserving vertex splits through specified corners (i.e., the gaps between pairs of consecutive edges that share a vertex and a face). We furthermore support changes to the embedding →E (G) in 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. Updates that are incompatible with the current upward planar embedding are identified and rejected.
All update operations are supported as long as the graph remains upward planar. In addition, we support queries that can tell whether two vertices can be connected with a directed edge while the graph remains single-source (we call these uplinkability queries). If a pair of vertices are not uplinkable, we facilitate one-flip-linkable queries: These point to a flip that makes them uplinkable, if any such flip exists. We dynamically maintain a linear-size data structure on G which supports incidence queries between a vertex and a face, and uplinkability queries for vertex pairs. We support all updates and queries in O(log²n) worst-case time.