8.1 Eliminating a Single Vertex

Assuming that the graph GG is represented by a list of vertices VGV(G) and a list of edges EGE(G), Algorithm 16 eliminates vertex vv from GG. It assumes the buffer ee provides communication with the edge list.

Algorithm 16: Eliminate a Vertex from a Graph
adjacency_list(V,EV,E)
for all vertices ww adjacent to vv
   for all vertices zz adjacent to vv
      if wzw\neq z and find(E,w,zE,w,z) is eoleol
         e.v=we.v=w
         e.w=ze.w=z
         link(E,1E,1)
   i=i=find(E,w,zE,w,z)
   unlink(E,iE,i)
i=i=find(V,vV,v)
unlink(V,iV,i)

The operation adjacency_list creates an adjacency list from VGV(G) and EGE(G). In Section 4, Algorithms 1 and Algorithm 3 were presented to solve this problem. New edges created during vertex elimination are arbitrarily inserted at the beginning of the edge list. For the current purposes, the insertion point is irrelevant.