Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Holm, Jacob; Italiano, Giuseppe F.; Karczmarz, Adam; Lacki, Jakub; Rotenberg, Eva http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-95091
URL:

; ; ; ;

Decremental SPQR-trees for Planar Graphs

pdf-format:


Abstract

We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over Omega(n) operations, is O(log^2 n). Via SPQR-trees, we give a decremental data structure for maintaining 3-vertex connectivity in planar graphs. It answers queries in O(1) time and processes edge deletions and contractions in O(log^2 n) amortized time. The previous best supported deletions and insertions in O(sqrt{n}) time.

BibTeX - Entry

@InProceedings{holm_et_al:LIPIcs:2018:9509,
  author =	{Jacob Holm and Giuseppe F. Italiano and Adam Karczmarz and Jakub Lacki and Eva Rotenberg},
  title =	{{Decremental SPQR-trees for Planar Graphs}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9509},
  URN =		{urn:nbn:de:0030-drops-95091},
  doi =		{10.4230/LIPIcs.ESA.2018.46},
  annote =	{Keywords: Graph embeddings, data structures, graph algorithms, planar graphs, SPQR-trees, triconnectivity}
}

Keywords: Graph embeddings, data structures, graph algorithms, planar graphs, SPQR-trees, triconnectivity
Seminar: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue date: 2018
Date of publication: 2018


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