# Drawing Graph Products

I need to draw graphs that are Cartesian products of 2 graphs. I need them to look like this: .

So each copy of the factors can have LinearEmbedding, but the whole drawing should be based on grid-like skeleton. Clearly, vertices should be on nodes of the grid, and edges can be arbitrary. Are there any solutions?

In particular, for Grid Graphs the SpringEmbedding gives similar result, but even for Torus Graphs result is very different. I need to draw Cartesian products of complete graphs, cycles, paths, complete bipartite graphs, and add labels to edges of the products.

-

I do feel that the question could be a bit more clear. When you write "each copy of the factors can have LinearEmbedding", do mean that each factor is, in fact, a path graph? Assuming so, perhaps something like the following could work. (Seems to complicated, I admit.)

m = 3;
n = 2;
g1 = Graph[
Table[UndirectedEdge[Subscript[u, i], Subscript[u, i + 1]], {i, 1, m - 1}],
VertexLabels -> "Name",
VertexCoordinates -> Table[{0, i}, {i, 1, m}]
];
g2 = Graph[
Table[UndirectedEdge[Subscript[u, i], Subscript[u, i + 1]], {i, 1, n - 1}],
VertexLabels -> "Name",
VertexCoordinates -> Table[{i, 0}, {i, 1, n}]
];
g1g2 = Graph[
Flatten@Join[
Table[
UndirectedEdge[{Subscript[u, i], Subscript[u, j]},
{Subscript[u, i], Subscript[u, j + 1]}], {i, 1, m}, {j, 1, n - 1}],
Table[
UndirectedEdge[{Subscript[u, i], Subscript[u, j]},
{Subscript[u, i + 1], Subscript[u, j]}], {i, 1, m - 1}, {j, 1, n}]
],
VertexLabels -> "Name",
VertexCoordinates -> Flatten[Table[{i, j}, {i, 1, m}, {j, 1, n}], 1]
];
size[1] = {100, 200};
size[2] = {200, 100};
size[3] = {300, 200};
Row[MapIndexed[Show[GraphComputationGraphConvertToGraphics[#],
ImageMargins -> 5, ImageSize -> size[#2[[1]]]] &,
{g1, g2, g1g2}],
ImageSize -> 700, Alignment -> Center]


The bulk of this code involves the layout of the graph. If you simply want a generalized Cartesian product of graphs without regard to the layout, then that's a bit easier.

SeedRandom[1];
g1 = RandomGraph[{5, 5},VertexLabels -> "Name"];
g2 = RandomGraph[{5, 8},VertexLabels -> "Name"];
makeCartesianProductEdge[u_, UndirectedEdge[u2_, v2_]] := UndirectedEdge[{u, u2}, {u, v2}];
makeCartesianProductEdge[UndirectedEdge[u1_, v1_], v_] := UndirectedEdge[{u1, v}, {v1, v}];
g1g2 = Graph[Flatten[{
Table[makeCartesianProductEdge[u, e],{u, VertexList[g1]}, {e, EdgeList[g2]}],
Table[makeCartesianProductEdge[e, u],{u, VertexList[g2]}, {e, EdgeList[g1]}]}],
VertexLabels -> "Name"];
graphToGraphics[g_Graph] := GraphComputationGraphConvertToGraphics[g];
graphToGraphics[else_] := else;
GraphicsGrid[Partition[graphToGraphics /@ {g1, g2, g1g2, SpanFromLeft}, 2]]


If you want a linear embedding of non-path graphs, then you'll need to do something to keep the edges from lying on top of one another.

g1 = Graph[EdgeList[g1], VertexCoordinates -> Table[{i, 0}, {i, 1, Length[VertexList[g1]]}]];
g2 = Graph[EdgeList[g2], VertexCoordinates -> Table[{i, 0}, {i, 1, Length[VertexList[g2]]}]];
g1g2 = Graph[EdgeList[g1g2], VertexCoordinates -> VertexList[g1g2]]


Perhaps the following EdgeShapeFunction will help, but I doubt it.

esf[{u_, v_}, ___] := {Opacity[0.3], Arrow[BSplineCurve[Table[
(u + v)/2 + Norm[v - u] {Cos[t], Sin[t]}/2,
{t, ArcTan @@ (v - u), ArcTan @@ (v - u) + Pi, Pi/5}]]]};
GraphicsRow[SetProperty[#, EdgeShapeFunction -> esf] & /@ {g1, g2, g1g2}]


-
@R.M I got the impression he was looking for the Cartesian product of arbitrary path graphs (note the parameters m and n). Hence, my question about linear embeddings. –  Mark McClure Apr 30 '12 at 4:09
I stand corrected. While my interpretation was the same as yours, I didn't pay closer attention to your code. Very nice! :) –  rm -rf Apr 30 '12 at 6:03
Thank you very much for the answer. I've noted that I need to draw Cartesian products of complete graphs, paths, cycles etc. If each factor is a path graph, then the product is GridGraph for which SpringEmbedding is nice. I wrote I needed LinearEmbedding because for GraphPlot that option produced a drawing with curved, non-overlapping edges, same result that you got using EdgeShapeFunction –  Hrant Khachatrian Apr 30 '12 at 8:07
So the last part of the answer is what I needed :) Two important things I learned: 1. how to effectively construct Cartesian product for Graph objects; 2. how to use EdgeShapeFunction. Hope this will be enough to achieve all my goals. Thanks again. –  Hrant Khachatrian Apr 30 '12 at 8:08
hmm.. I couldn't recreate the last drawings you've attached. Output for your code is SetProperty[ (* image here *), EdgeShapeFunction->esf], so it doesn't work. I tried to use your EdgeShapeFunction for g1 only: Graph[EdgeList[g1], EdgeShapeFunction -> esf, VertexCoordinates -> Table[{i, 0}, {i, 1, Length[VertexList[g1]]}]] and I get ArcTan::indet: "Indeterminate expression ArcTan[0.,0.] encountered.". –  Hrant Khachatrian Apr 30 '12 at 8:32