2026-07-20T12:07:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21141 2024-09-23T09:13:18Z ddc:004 open_access

Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs van der Hoog, Ivor Parada, Irene Rotenberg, Eva dynamic graphs data structures computational geometry graph drawing graph algorithms upward planarity 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 ℰ→(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 ℰ→(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ivor van der Hoog and Irene Parada and Eva Rotenberg 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.70 urn:nbn:de:0030-drops-211410 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.70 eng https://creativecommons.org/licenses/by/4.0/legalcode