We consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms and data structures for maintaining information about 2- and 3-vertex-connectivity, and 3- and 4-edge-connectivity in a planar graph in O(n1/2) amortized time per insertion, deletion, or connectivity query. All of the data structures handle insertions that keep the graph planar without regard to any particular embedding of the graph. Our algorithms are based on a new type of sparsification combined with several properties of separators in planar graphs.

Separator based sparsification II: edge and vertex connectivity / Eppstein, D.; Galil, Z.; Italiano, Giuseppe Francesco; Spencer, T.. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 28:1(1999), pp. 341-381. [10.1137/S0097539794269072]

Separator based sparsification II: edge and vertex connectivity

ITALIANO G;
1999

Abstract

We consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms and data structures for maintaining information about 2- and 3-vertex-connectivity, and 3- and 4-edge-connectivity in a planar graph in O(n1/2) amortized time per insertion, deletion, or connectivity query. All of the data structures handle insertions that keep the graph planar without regard to any particular embedding of the graph. Our algorithms are based on a new type of sparsification combined with several properties of separators in planar graphs.
1999
Separator based sparsification II: edge and vertex connectivity / Eppstein, D.; Galil, Z.; Italiano, Giuseppe Francesco; Spencer, T.. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 28:1(1999), pp. 341-381. [10.1137/S0097539794269072]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/199829
Citazioni
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 16
  • OpenAlex ND
social impact