I am interested in finding a program which can calculate and preferably also visualize various products of not huge graphs.

More specifically, I work with labeled, directed multigraphs, and would like to be able to calculate and visualize especially the lexicographic product of such graphs.

Further, as it more precisely is a close variant of the lexicographic product I am interested in, it would be preferable if modifying the predefined operation is possible.

Specifically, I am interested in the following: where L(sG) constitute the set of labels on node s in graph G, and pre(tH) is one of two sets of labels for t in H, the product is one such that 1) the set of nodes is (s,t) such that pre(tH) is a subset of L(sG), 2) (s,t) and (s',t') are related in GxH as specified by the lexicographic product, and 3) the labels L(sGxH) are [those from L(sG) plus those from the second set of labels of t in H called post(t,H)] minus [those from L(sG) inconsistent with the new post(t,H)].

I do not assume that the program in question has the specified operation pre-programmed, but it would be very nice if it was implementable with some tampering.

Does any one know of a package that would allow this?

  • $\begingroup$ Your edit is better suited as a comment on @jernej's post $\endgroup$ Commented Nov 30, 2012 at 16:37
  • $\begingroup$ I don't quite follow what do you mean by "close variant". Can you describe more precisely what exactly do you want? $\endgroup$
    – Jernej
    Commented Dec 1, 2012 at 12:31
  • $\begingroup$ Of course. I have done so now. I hope this is specific enough -- further details, I'm afraid, would require auxiliary definitions. $\endgroup$
    – Rasmus
    Commented Dec 4, 2012 at 18:18
  • $\begingroup$ In terms of calculating the adjacency, for most products of graphs, it simply involves Kronecker products of the original adjacencies wiki.canisiusmath.net/… $\endgroup$
    – Dimitris
    Commented Dec 6, 2012 at 18:15

2 Answers 2


I think that Sage is the right thing for this task.


sage: G = digraphs.Circuit(40)  
sage: G = G.lexicographic_product(G)
sage: G.show()

Other graph products and algorithms are available as well.


try also this recent ref:

Visualization of Graph Products by Janicke et al, IEEE Transactions on Visualization and Computer Graphics (2010)

... Graph products constitute a class that arises frequently in graph theory, but for which no visualization algorithm has been proposed until now. In this paper, we present an algorithm for drawing graph products and the aesthetic criterion graph product's drawings are subject to. We show that the popular High-Dimensional Embedder approach applied to cartesian products already respects this aestetic criterion, but has disadvantages. We also present how our method is integrated as a new component into the TopoLayout framework. Our implementation is used for further research of graph products in a biological context.


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.