License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.434
URN: urn:nbn:de:0030-drops-49319
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4931/
Go to the corresponding LIPIcs Volume Portal

Holm, Jacob ; Rotenberg, Eva

Dynamic Planar Embeddings of Dynamic Graphs

pdf-format:
31.pdf (0.7 MB)

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 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, 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 will 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.

BibTeX - Entry

@InProceedings{holm_et_al:LIPIcs:2015:4931,
  author =	{Jacob Holm and Eva Rotenberg},
  title =	{{Dynamic Planar Embeddings of Dynamic Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{434--446},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4931},
  URN =		{urn:nbn:de:0030-drops-49319},
  doi =		{10.4230/LIPIcs.STACS.2015.434},
  annote =	{Keywords: dynamic graphs, planar embeddings, data structures}
}

Keywords: dynamic graphs, planar embeddings, data structures
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI