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

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.


1 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[
      UndirectedEdge[{Subscript[u, i], Subscript[u, j]}, 
        {Subscript[u, i], Subscript[u, j + 1]}], {i, 1, m}, {j, 1, n - 1}],
      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};
    ImageMargins -> 5, ImageSize -> size[#2[[1]]]] &, 
  {g1, g2, g1g2}],
 ImageSize -> 700, Alignment -> Center]

enter image description here

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.

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]]

enter image description here

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]]

enter image description here

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}]

enter image description here

  • $\begingroup$ @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. $\endgroup$ Commented Apr 30, 2012 at 4:09
  • $\begingroup$ I stand corrected. While my interpretation was the same as yours, I didn't pay closer attention to your code. Very nice! :) $\endgroup$
    – rm -rf
    Commented Apr 30, 2012 at 6:03
  • $\begingroup$ 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 $\endgroup$ Commented Apr 30, 2012 at 8:07
  • $\begingroup$ 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. $\endgroup$ Commented Apr 30, 2012 at 8:08
  • $\begingroup$ 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.". $\endgroup$ Commented Apr 30, 2012 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.