---
_id: '11681'
abstract:
- lang: eng
  text: We prove lower bounds on the complexity of maintaining fully dynamic k -edge
    or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs.
    We show an amortized lower bound of Ω (log n / {k (log log n} + log b)) per edge
    insertion, deletion, or query operation in the cell probe model, where b is the
    word size of the machine and n is the number of vertices in G . We also show an
    amortized lower bound of Ω (log n /(log log n + log b)) per operation for fully
    dynamic planarity testing in embedded graphs. These are the first lower bounds
    for fully dynamic connectivity problems.
acknowledgement: .
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: M. L.
  full_name: Fredman, M. L.
  last_name: Fredman
citation:
  ama: Henzinger MH, Fredman ML. Lower bounds for fully dynamic connectivity problems
    in graphs. <i>Algorithmica</i>. 1998;22(3):351-362. doi:<a href="https://doi.org/10.1007/pl00009228">10.1007/pl00009228</a>
  apa: Henzinger, M. H., &#38; Fredman, M. L. (1998). Lower bounds for fully dynamic
    connectivity problems in graphs. <i>Algorithmica</i>. Springer Nature. <a href="https://doi.org/10.1007/pl00009228">https://doi.org/10.1007/pl00009228</a>
  chicago: Henzinger, Monika H, and M. L. Fredman. “Lower Bounds for Fully Dynamic
    Connectivity Problems in Graphs.” <i>Algorithmica</i>. Springer Nature, 1998.
    <a href="https://doi.org/10.1007/pl00009228">https://doi.org/10.1007/pl00009228</a>.
  ieee: M. H. Henzinger and M. L. Fredman, “Lower bounds for fully dynamic connectivity
    problems in graphs,” <i>Algorithmica</i>, vol. 22, no. 3. Springer Nature, pp.
    351–362, 1998.
  ista: Henzinger MH, Fredman ML. 1998. Lower bounds for fully dynamic connectivity
    problems in graphs. Algorithmica. 22(3), 351–362.
  mla: Henzinger, Monika H., and M. L. Fredman. “Lower Bounds for Fully Dynamic Connectivity
    Problems in Graphs.” <i>Algorithmica</i>, vol. 22, no. 3, Springer Nature, 1998,
    pp. 351–62, doi:<a href="https://doi.org/10.1007/pl00009228">10.1007/pl00009228</a>.
  short: M.H. Henzinger, M.L. Fredman, Algorithmica 22 (1998) 351–362.
date_created: 2022-07-28T06:58:36Z
date_published: 1998-11-01T00:00:00Z
date_updated: 2022-09-12T09:03:36Z
day: '01'
doi: 10.1007/pl00009228
extern: '1'
intvolume: '        22'
issue: '3'
keyword:
- Dynamic planarity testing
- Dynamic connectivity testing
- Lower bounds
- Cell probe model
language:
- iso: eng
month: '11'
oa_version: None
page: 351-362
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds for fully dynamic connectivity problems in graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '1998'
...