Data structure for adjacent rectangles
The sweeping algorithm, suggested by @adrianN, can be elaborated this way.

Step 1. Put all your rectangles in a map of sets in such way, that:


the map key is left boundary of rectangle
the map value is ordered by lower boundary set of rectangles, having this left boundary


For your example, this map will be:


0 => (2, 5, 10)
4 => (6, 7, 11)
8 => (3, 4)
11 => (9, 12)
15 => (8)
19 => (1)


Step 2. Create a similar map of rectangle sets, having the same right boundary.  

Step 3. Define active rectangle set, which will "sweep" the data structure above, from left to right, generating pairs of adjacent rectangles.

At first assign to the active set the rectangle set with minimal left boundary $x_0$. You can immediately generate a number of pairs of adjacent rectangles from the active set (because it's ordered and there are no "holes" in it).

Then move the active set to the next position of the left boundary, let's say $x_1$. You will need to update the active set, removing rectangles with right boundary $x_1$, and adding rectangles with left boundary $x_1$. You already have these rectangle sets in data structures, created earlier. The active set will be ordered after this update - generate pairs from it.

And so on...

For your example - active sets A0, A1 etc. will be:


A0 = (2, 5, 10)
A1 = (5, 6, 7, 11)
A2 = (5, 6, 4, 3)
A3 = (9, 6, 4, 12)
A4 = (9, 8, 4, 12)
A5 = (1)


This algorithm will generate all pairs of rectangles, adjacent in vertical direction only. Some of pairs will be generated more than once - you'll need to filter repetitions out.

In order to get all pairs of rectangles, adjacent in horizontal direction, you'll need to "rotate the picture" by 90 grades and repeat the algorithm. Another option - much more complex processing of rectangles during the active set update.

Time complexity of this algorithm depends on complexity of set operations union and minus.