We describe algorithms and data structures for maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We give a fully dynamic planarity testing algorithm that maintains a graph subject to edge insertions and deletions and that allows queries that test whether the graph is currently planar, or whether a potential new edge would violate planarity, inO(n1/2) amortized time per update or query. We give fully dynamic algorithms for maintaining the connected components, the best swap and the minimum spanning forest of a planar graph inO(log n) worst-case time per insertion andO(log2 n) per deletion. Finally, we give fully dynamic algorithms for maintaining the 2-edge-connected components of a planar graph inO(log n) amortized time per insertion andO(log2 n) per deletion. All of the data structures, except for the one that answers planarity queries, handle only insertions that keep the graph planar. All our algorithms improve previous bounds. The improvements are based upon a new type of sparsification combined with several properties of separators in planar graphs.

Separator based sparsification I: planarity testing and minimum spanning trees / Eppstein, D.; Galil, Z.; Italiano, Giuseppe Francesco; Spencer, T.. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 52:1(1996), pp. 3-27. [10.1006/jcss.1996.0002]

Separator based sparsification I: planarity testing and minimum spanning trees

ITALIANO G;
1996

Abstract

We describe algorithms and data structures for maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We give a fully dynamic planarity testing algorithm that maintains a graph subject to edge insertions and deletions and that allows queries that test whether the graph is currently planar, or whether a potential new edge would violate planarity, inO(n1/2) amortized time per update or query. We give fully dynamic algorithms for maintaining the connected components, the best swap and the minimum spanning forest of a planar graph inO(log n) worst-case time per insertion andO(log2 n) per deletion. Finally, we give fully dynamic algorithms for maintaining the 2-edge-connected components of a planar graph inO(log n) amortized time per insertion andO(log2 n) per deletion. All of the data structures, except for the one that answers planarity queries, handle only insertions that keep the graph planar. All our algorithms improve previous bounds. The improvements are based upon a new type of sparsification combined with several properties of separators in planar graphs.
1996
Separator based sparsification I: planarity testing and minimum spanning trees / Eppstein, D.; Galil, Z.; Italiano, Giuseppe Francesco; Spencer, T.. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - 52:1(1996), pp. 3-27. [10.1006/jcss.1996.0002]
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/199843
Citazioni
  • Scopus 45
  • ???jsp.display-item.citation.isi??? 27
social impact