Dynamic Algorithms for Graphs with Treewidth 2

Abstract

In this paper, we consider algorithms for maintaining tree-decompositions with constant bounded treewith under edge and vertex insertions and deletions for graphs with treewith at most 2 (also called: partial 2-trees, or series-parallel graphs), and for almost trees with parameter k. Each operation can be performed in O(log n) time. For a large number of graph decision, optimization and counting problems, information can be maintained using O(log n) time per update, such that queries can be resolved in O(log n), or O(1) time. Similar results hold for the classes of almost tress with parameter k, for fixed k.