Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(sorry if i use some strange word. english is not my native language so i am not sure about all the mathematical terms)

I need to draw some graphs that all have some common features.

  • the vertices are tuples $(i,j)$ with $i=1,\dots,n$ and $j=1,\dots,k$.
  • two vertices $(i_1, j_1), (i_2, j_2)$ share an edge if and only if $i_1\ne i_2$ and $j_1\ne j_2$.

So these graphs look a lot like complete $k$-partite graphs.

My question is how to best draw them. I tried simple dot like this:

graph g_2_3 {
  "0 0" -- "1 1";
  "0 0" -- "1 2";
  "0 1" -- "1 0";
  "0 1" -- "1 2";
  "0 2" -- "1 0";
  "0 2" -- "1 1";

But this looks too messy to use it for illustrating something.

share|cite|improve this question
best draw them? on what? – nbubis Jan 21 '13 at 11:01
@nbubis sorry. I meant to draw using a computer – user59096 Feb 21 '13 at 10:56

You could place the vertices of the graph at the vertices $n$-gons that are centered at the vertices of a large $k$-gon.

For instance, for $(n,k) = (3,5)$:

3-gons about a 5-gon

Here, triangles are arranged about a pentagon. You can see, for instance, that the "outermost" vertex of each triangle is connected to the "other two" vertices.

Writing $R$ for the radius of the larger $k$-gon, and $r$ for the radius of each smaller $n$-gon, and defining $T := 2\pi/k$ and $t := 2\pi/n$, we can say explicitly that vertex/tuple $(i,j)$ is located at coordinates

$$( \; R \cos( j T ) + r \cos( i t + j T ), R \sin(jT) + r \sin(it + jT ) \; )$$

share|cite|improve this answer

One possibility: instead of visualizing this graph, start by visualizing its complement. That is a much "nicer" graph; e.g., you can just arrange all the dots in an $n \times m$ matrix, in which case the joined vertices are precisely the vertices sharing a row or column. Now if you want to see your actual graph, it should be relatively easy from that point to visualize complementing the complement. In linear algebra terms a vertex $(i,j)$ is then joined to everything in the $(i,j)$-minor.

Another question (whose answer depends on your application): is a graph really the best way to think about whatever this is? Graphs are usually a concept that one would apply when one has a rather complex and irregular data set to analyze. Perhaps in this case one could do away with the graph and think in simpler terms; e.g., just talking about a binary relation between points?

share|cite|improve this answer
Isn't an (undirected) graph excaly that: A binary relation between points? But anyway, the graph is not only a graph but a cw-complex, so I really need to think of it as a graph. But thanks for the great idea about complmenets. I will think about that! – user59096 Jan 21 '13 at 12:55
PS. The complement is the rook's graph. – Douglas S. Stones Apr 10 '13 at 13:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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