8.1 Eliminating a Single Vertex

Assuming that the graph $G$ is represented by a list of vertices $V(G)$ and a list of edges $E(G)$ , Algorithm 16 eliminates vertex $v$ from $G$ . It assumes the buffer $e$ provides communication with the edge list.

Algorithm 16: Eliminate a Vertex from a Graph

adjacency_list(

V,E

)

for all vertices

w

adjacent to

v

for all vertices

z

adjacent to

v

w\neq z

and find(

E,w,z

) is

eol

e.v=w

e.w=z

link(

E,1

)

i=

find(

E,w,z

)

unlink(

E,i

)

i=

find(

V,v

)

unlink(

V,i

)

The operation adjacency_list creates an adjacency list from $V(G)$ and $E(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.