Maintaining the connectivity of a dynamic graph is a basic problem in data structure design. A dynamic graph is continuously subjected to changes such as single insertions or deletions of edges and vertices. As a connectivity data structure has to answer the question if two vertices in a graph are connected, it is sufficient to know the connected components. These can dramatically change with the deletion of one point which is incident to many (otherwise) disjoint subgraphs. Thus, the efficient handling of the connected components is crucial.

The problem becomes more challenging when the dynamic graph, whose connectivity should be maintained, is an intersection graph. In intersection graphs, the vertices represent point sets and there is an edge if and only if two sets intersect. Hence, a dynamic connectivity data structure for intersection graphs also has to determine which edges are affected by the insertion or deletion of one vertex.

The dynamic data structure for unit disk graphs by Kaplan et al. was used as a basis for this thesis. An unit disk graph is defined by a set of unit disks represented by their centers. Their data structure achieves an amortized update time of O(log n log log n) and a worst-case query time of O(log n) for connectivity queries.

In this thesis the data structure was adapted for unit squares. This means, that the point sets for the intersection graph are unit squares, represented by their centers. The developed data structure is able to maintain connectivity for axis-aligned unit squares and unit squares rotated by 45°. For this purpose, an adaptation of AVL trees is devised which supports a faster detection of edges. Hence, the connectivity data structure achieves an amortized update time of O(log n) and a worst-case query time of O(log n) for connectivity queries.