Decremental SPQR-trees for planar graphs
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- OA-Decremental SPQR-trees for Planar Graphs
Final published version, 508 KB, PDF document
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 Ω(n) operations, is O(log2 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(log2 n) amortized time. The previous best supported deletions and insertions in O(√n) time.
| Original language | English |
|---|---|
| Title of host publication | 26th European Symposium on Algorithms, ESA 2018 |
| Editors | Hannah Bast, Grzegorz Herman, Yossi Azar |
| Number of pages | 16 |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Publication date | 1 Aug 2018 |
| Article number | 46 |
| ISBN (Print) | 9783959770811 |
| DOIs | |
| Publication status | Published - 1 Aug 2018 |
| Event | 26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland Duration: 20 Aug 2018 → 22 Aug 2018 |
Conference
| Conference | 26th European Symposium on Algorithms, ESA 2018 |
|---|---|
| Land | Finland |
| By | Helsinki |
| Periode | 20/08/2018 → 22/08/2018 |
| Series | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 112 |
| ISSN | 1868-8969 |
- Data structures, Graph algorithms, Graph embeddings, Planar graphs, SPQR-trees, Triconnectivity
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
No data available
ID: 230343791