Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs

Research output: Contribution to journalConference articleResearchpeer-review

2 Downloads (Pure)

Abstract

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(log2n) worst-case time.
Original languageEnglish
Article number70
JournalLeibniz International Proceedings in Informatics, LIPIcs
Volume308
Number of pages18
ISSN1868-8969
DOIs
Publication statusPublished - 2024
Event32nd Annual European Symposium on Algorithms - London, United Kingdom
Duration: 2 Sept 20244 Sept 2024

Conference

Conference32nd Annual European Symposium on Algorithms
Country/TerritoryUnited Kingdom
CityLondon
Period02/09/202404/09/2024

Keywords

  • Computational geometry
  • Data structures
  • Dynamic graphs
  • Graph algorithms
  • Graph drawing
  • Upward planarity

Fingerprint

Dive into the research topics of 'Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs'. Together they form a unique fingerprint.

Cite this