A program’s call graph is an essential underlying structure for performing the various interprocedural analyses used in software development tools for object-oriented software systems. For interactive software development tools and software maintenance activities, the call graph needs to remain fairly precise and be updated quickly in response to software changes. This paper presents incremental algorithms for updating a call graph that has been initially constructed using the Cartesian Product Algorithm, which computes a highly precise call graph in the presence of dynamically dispatched message sends. Templates are exploited to reduce unnecessary reanalysis as software component changes occur. The preliminary empirical results from our implementation within a Java environment are encouraging. Significant time savings were observed for the incremental algorithm comparison to an exhaustive analysis, with no loss in precision.