We present a three-part article comprising a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science commu­nity. This article presents the first part of the survey outlin­ing the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part of the survey, we will present a set of techniques to prove up­per bounds for dynamic graph problems. In the third part of the survey, we will present a set of techniques to prove lower bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of lower bounds and upper bounds results for their dynamic graph counterparts. Along with theoretical advances, the techniques used in dynamic graphs need attention from an implementation perspective. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey. The survey can also be used to understand the first algorithms for several recent dynamic graph algorithms.

We present a three-part article consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. This article presents the second part of the survey consisting of a set of techniques to prove upper bounds for dynamic graph problems. In the first part of the survey, we presented motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the third part of the survey, we will present a set of techniques to prove lower bounds for dynamic graph problems.

A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of upper bound results for their dynamic graph counterparts. The upper bound techniques used in dynamic graphs need attention from an implementation perspective, along with theoretical advances. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey.

We present a three-part paper consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. In this third part of the three-part survey paper, we present a set of techniques to prove lower bounds for dynamic graph problems. In the first part\mfnote{\textit{Resonance}, Vol.27, No.8, pp.1443--1451, August 2022.} of the survey, we presented the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part\mfnote{\textit{Resonance}, Vol.27, No.9, pp.1607-1624, September 2022.} of the survey, we presented a set of techniques to prove upper bounds for dynamic graph problems.

A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Research in dynamic graphs has succeeded in obtaining efficient upper bounds for an extensive collection of problems. However, there are problems of stubborn nature. Such complex problems lead to the investigation of lower bounds.