I would assume here that adding/removing edges/vertices will be done one at a time. Please take note, the term node is used for a node in a linked list and I tried my best not to use it interchangeably with the term vertex.
The structures for storing vertices and edges
A be your adjacency list for the graph.
V be an array (ordinary/associative depending on your actual vertex representation) of pointers. An entry in
V points to a vertex stored in the structure
D given below.
D be a doubly linked list. A node
n of this list holds two data:
d an integer that represents the degree and a doubly linked list
l containing all vertices with degree
d. We shall maintain that the nodes of
D are ordered in increasing value of
d. You can think of nodes in
D like a bucket containing all vertices with the same degrees.
D will have a tail pointer that points to the end (bucket containing vertices with maximal degree).
D only has a node
n0 such that
n0.d = 0, which will contain all newly added vertex (assuming that newly added vertex has no edge yet).
The entries of list
l are vertices with degree
d. Each vertex
l has a pointer
b that points back to the node in
Adding a new vertex
When you add a new vertex
v, create an entry in
A and add it to
n0.l and finally add an entry in
V that will point to
Adding and removing edges
When a new edge
(u,v) is added, add the nodes (using the procedure above) if they do not exist yet. Update the entries of
A. Then, follow the pointer of
V. At this point, the degree of
u will increase by 1. Follow
u.b pointer to get the node
n' be the node following
n.d + 1, transfer
n' does not exists or
n'.d > n.d + 1, insert a new node
n such that
m.d = n.d + 1 and transfer
u to this node. Update
u.b. If after this
n.l becomes empty , delete it, except when
n = n0. Do the same update to vertex
v. Finally, update the tail pointer of
D in case the the last node in
When you remove an edge, you can simply reverse the process of adding (I will leave this one for you to think about).
Removing a vertex
Removing a vertex
v can be implemented by first removing all its edges one at a time using the edge removal procedure above, then finally removing
Updating the edges of a vertex and maintaining the order of
D after adding a vertex and updating edges takes $O(1)$ time (ignoring the cost of adding a new entry in
V which is dependent on how you implement them). This is because we only need to follow and update constant number of pointers and create/remove constant number of nodes in the linked lists.
As for the removal of a vertex
v, the time is $O(deg(v))$, which I think is optimal since you have to update that many vertices too since you have to update the neighbors of the removed vertex.
Each entire representation requires $O(n)$ extra space for the pointers and linked list nodes for each vertex. This is $O(1)$ additional space per vertex.