>I am not familiar with METIS at all, so is there a way to
> provide the underlying graph in a more intuitive format? An actual image would
> be nice. Or again, the dot-output for graphviz?

An image of the graph distributed among two processes.
http://lamberti.web.cs.unibo.it/bfs.png

If i get your point, process 0 starts a bfs with the n0 as root and process 1 starts with n4 as root cause n0 and n4 are the local node 0 of each process. And the ouput is the minimum distance value of each node discovered via n0 and n4 either?
To what end?

This is the ouput with three processes:

graph g {
subgraph cluster_0 {
    label="p0";
    n0[label=0];
    n1[label=0];
}

n0 -- n2;
n1 -- n1;
n1 -- n3;
n1 -- n4;

subgraph cluster_1 {
    label="p1";
    n2[label=0];
    n3[label=1];
}

n2 -- n1;
n2 -- n3;
n3 -- n4;

subgraph cluster_2 {
    label="p2";
    n4[label=0];
}

n4 -- n0;
n4 -- n1;
}

This seems to confirm your explanation (at least what i understood of your explanation).

--
Best regards,
Mattia