DYNAMIC GRAPH MODELS

Research in graph theory has focused on studying the structure of grap hs with the assumption that they are static. However, in many applicat ions, the graphs that arise change with time, i.e., they are dynamic i n nature. This is especially true of applications involving graph mode ls in computer science. We present an expository study of dynamic grap hs with the main driving force being practical applications. We first develop a formal classification of dynamic graphs. This taxonomy in th e form of generalizations and extensions will in turn suggest new area s of application. Next, we discuss areas where dynamic graphs arise in computer science such as compilers, databases, fault-tolerance, artif icial intelligence, and computer networks. Finally, we propose approac hes that can be used for studying dynamic graphs. The main objective i n any study of dynamic graphs should be to (i) extend results develope d for static graph theory to dynamic graphs, (ii) study the properties that describe how a dynamic graph changes, (iii) investigate problems and issues in dynamic graph theory that are raised by practical appli cations of dynamic graphs in computer science.