Drawing Graph Products

Question

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.

Answer 1

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[GraphComputation`GraphConvertToGraphics[#],
    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] := GraphComputation`GraphConvertToGraphics[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}]