---
_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'
...
---
_id: '4097'
abstract:
- lang: eng
  text: Arrangements of curves in the plane are of fundamental significance in many
    problems of computational and combinatorial geometry (e.g. motion planning, algebraic
    cell decomposition, etc.). In this paper we study various topological and combinatorial
    properties of such arrangements under some mild assumptions on the shape of the
    curves, and develop basic tools for the construction, manipulation, and analysis
    of these arrangements. Our main results include a generalization of the zone theorem
    of [EOS], [CGL] to arrangements of curves (in which we show that the combinatorial
    complexity of the zone of a curve is nearly linear in the number of curves), and
    an application of (some weaker variant of) that theorem to obtain a nearly quadratic
    incremental algorithm for the construction of such arrangements.
acknowledgement: Work on this paper by the first author has been supported by Amoco
  Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under
  grant CCR-8714566. Work on this paper by the third and sixth authors has been supported
  by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation
  Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and
  the IBM Corporation. Work by the sixth author has also been supported by a research
  grant from the NCRD — the Israeli National Council for Research and Development.
  Work by the fourth author has been supported by National Science Foundation Grant
  DMS-8501947.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: János
  full_name: Pach, János
  last_name: Pach
- first_name: Richard
  full_name: Pollack, Richard
  last_name: Pollack
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  ama: 'Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. Arrangements
    of curves in the plane - topology, combinatorics, and algorithms. In: <i>15th
    International Colloquium on Automata, Languages and Programming</i>. Vol 317.
    Springer; 1988:214-229. doi:<a href="https://doi.org/10.1007/3-540-19488-6_118">10.1007/3-540-19488-6_118</a>'
  apa: 'Edelsbrunner, H., Guibas, L., Pach, J., Pollack, R., Seidel, R., &#38; Sharir,
    M. (1988). Arrangements of curves in the plane - topology, combinatorics, and
    algorithms. In <i>15th International Colloquium on Automata, Languages and Programming</i>
    (Vol. 317, pp. 214–229). Tampere, Finland: Springer. <a href="https://doi.org/10.1007/3-540-19488-6_118">https://doi.org/10.1007/3-540-19488-6_118</a>'
  chicago: Edelsbrunner, Herbert, Leonidas Guibas, János Pach, Richard Pollack, Raimund
    Seidel, and Micha Sharir. “Arrangements of Curves in the Plane - Topology, Combinatorics,
    and Algorithms.” In <i>15th International Colloquium on Automata, Languages and
    Programming</i>, 317:214–29. Springer, 1988. <a href="https://doi.org/10.1007/3-540-19488-6_118">https://doi.org/10.1007/3-540-19488-6_118</a>.
  ieee: H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir,
    “Arrangements of curves in the plane - topology, combinatorics, and algorithms,”
    in <i>15th International Colloquium on Automata, Languages and Programming</i>,
    Tampere, Finland, 1988, vol. 317, pp. 214–229.
  ista: 'Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. 1988. Arrangements
    of curves in the plane - topology, combinatorics, and algorithms. 15th International
    Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages
    and Programming, LNCS, vol. 317, 214–229.'
  mla: Edelsbrunner, Herbert, et al. “Arrangements of Curves in the Plane - Topology,
    Combinatorics, and Algorithms.” <i>15th International Colloquium on Automata,
    Languages and Programming</i>, vol. 317, Springer, 1988, pp. 214–29, doi:<a href="https://doi.org/10.1007/3-540-19488-6_118">10.1007/3-540-19488-6_118</a>.
  short: H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, M. Sharir, in:,
    15th International Colloquium on Automata, Languages and Programming, Springer,
    1988, pp. 214–229.
conference:
  end_date: 1988-07-15
  location: Tampere, Finland
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 1988-07-11
date_created: 2018-12-11T12:06:55Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T10:15:09Z
day: '01'
doi: 10.1007/3-540-19488-6_118
extern: '1'
intvolume: '       317'
keyword:
- line segment
- computational geometry
- Jordan curve
- cell decomposition
- vertical tangency
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-19488-6_118
month: '01'
oa_version: None
page: 214 - 229
publication: 15th International Colloquium on Automata, Languages and Programming
publication_identifier:
  isbn:
  - 978-3-540-19488-0
publication_status: published
publisher: Springer
publist_id: '2028'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Arrangements of curves in the plane - topology, combinatorics, and algorithms
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 317
year: '1988'
...