Does Kernighan-Lin algorithm guarantee its partitions to be a connected graph? Currently I am experimenting with Kernighan-Lin algorithm to produce coarse representation of navigation mesh for hierarchical pathfinding.

Based on the use case, my requirement is that partitions produced are a connected graph on its own.

For example, a bisection of the below grid

x--x--x--x--x--x
|  |  |  |  |  |
x--x--x--x--x--x
|  |  |  |  |  |
x--x--x--x--x--x


Should produce something along the lines of

a--a--a--b--b--b
|  |  |  |  |  |
a--a--a--b--b--b
|  |  |  |  |  |
a--a--a--b--b--b


where all nodes in partition A can be reached from a node in partition A without crossing a node in partition B.

However in quite a number of tests, I am getting disconnected partitions such as.

a--b--b--b--a--a
|  |  |  |  |  |
a--b--b--b--a--a
|  |  |  |  |  |
b--b--b--a--a--a


I am not able to judge if this is a bug in my code or whether the Kernighan-Lin algorithm by nature does not guarantee connected partitions.

I know that KL algorithm works towards a locally optimal solution for minimum cut, but does the algorithm not guarantee connected partitions?
The Kernighan-Lin algorithm tries to find a partition.  As far as I can tell, the partition it finds might or might not be connected; I don't see any guarantee that it will output a connected partition.  There is also no guarantee that it finds the optimal partition.  Even if the optimal partition is connected, I don't think there is any guarantee that the Kernighan-Lin algorithm will output a connected partition.