I am making an engine for the game of Hive (

The graph with 18 vertices (black) is shown on the left. The corresponding block-cut tree is shown to the right. Notice that the cut points (aka articulation points) are considered to be part of the blocks that they connect. So for example, cut point 1 (C1) in the tree, which is vertex 2 (V2) in the graph is a member of blocks B1, B2, and B3.

I propose to add vertex 19 (magenta), and then consider the consequences. I've circled the cut points in the graph. Those circled in red (V2, V8, and V10) remain as cut points when V19 is added. But V7 (aka C2) ceases to be a cut point when V19 is added. That's because C2 in the block-cut tree is part of a cycle that is created by adding V19. And unlike C1, C3, and C4, it doesn't connect to any blocks that aren't part of the cycle. It only connects B3 and B4, which are both part of the cycle.

So after adding V19, there are only 4 blocks and 3 cut points. B2, B5, and B7 continue to exist as separate blocks, connected by C1, C3, and C4 respectively. B1, C1, B3, C2, B4, C3, C4, and B6 are now all part of a single large block. The resulting block-cut tree is shown below (source:ibid with modifications in color):

Finally getting to the point, notice that V7 is about as far away from V19 as it can possibly be. So the effects of adding a vertex aren't localized to the neighbors of the added vertex. The effects can propagate throughout the graph.

And then it gets worse.

We've seen the effects of adding a vertex. Now consider the reverse. After adding V19, the player decides to move the piece that V19 represents, thereby removing V19 from the graph. Suddenly, block B19 explodes into four blocks (B1, B3, B4, and B6), and C2 appears as a cut point. Basically restructuring the entire block-cut tree. So by the time the code finds the newly formed cut point, and rearranges the block-cut tree, it may have been possible (or even faster) to run Tarjan's again.