Based on the cell decomposition of images vertices and edges are also added. Generally, adding a new vertex creates a new component and a new node in the graph. Adding a new edge either connects two components or creates a hole in an existing component. Adding the cell itself eliminates a 1-cycle.
Now, let's consider the step of adding a single pixel to a black image. The pixel consists of 9 parts numbered as follows:
- vertices 1-4,
- edges 5-8,
- pixel itself 9.
They are added in this order illustrated below.
- Stage 1: 4 vertices (1-4) are added and exist as separate 0-cycles, A, B, C, D.
- Stage 2: as we add the first edge (5) two of these cycles (1 and 2) merge into one, E. As we add the next edge (6), the third 0-cycle (3) joins them, F. Adding the third edge (7) merges vertex (4) with the rest. At this point all we have is a single 0-cycle, G.
- Stage 3: adding the fourth edge (8) changes the 0-cycle, H, and creates a 1-cycle, I.
- Stage 4: adding the cell itself (9) eliminates cycle I.
In the image below, adding 1st pixel takes 9 steps, 2-6th 6 steps each, 7th 5 steps, and 8th 4 steps. More details on this example here .
If we omit the intermediate steps of adding edges and vertices, the graph looks much simpler. Here is an example: 8 pixels arranged in a square. The pixels, 1-8, are added one by one. After the first one there are no new cycles until pixel 7 which creates a new 1-cycle.
Exercise. Plot the graph for this image (Gridface). Answer