Dynamic planar embeddings of dynamic graphs

DOI10.4230/LIPICS.STACS.2015.434zbMATH Open1356.68161arXiv1704.00565OpenAlexW2621573206MaRDI QIDQ2955014FDOQ2955014

Authors: Jacob Holm, Eva Rotenberg 

Publication date: 24 January 2017

Abstract: We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices. Given vertices $u,v$, linkable$(u,v)$ decides whether $u$ and $v$ are linkable in the current embedding, and if so, returns a list of suggestions for the placement of $(u,v)$ in the embedding. For non-linkable vertices $u,v$, we define a new query, one-flip-linkable$(u,v)$ providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log${}^{2}n$) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph. Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.

Full work available at URL: https://arxiv.org/abs/1704.00565

Recommendations

• Dynamic planar embeddings of dynamic graphs
• On-line Planar Graph Embedding
• scientific article; zbMATH DE number 4060744
• Fully dynamic planarity testing with applications
• scientific article; zbMATH DE number 176746

zbMATH Keywords

data structuresdynamic graphsplanar embeddings

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (3)

• Dynamic maintenance of planar digraphs, with applications
• Dynamic planar embeddings of dynamic graphs
• Title not available (Why is that?)

This page was built for publication: Dynamic planar embeddings of dynamic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955014)