# Best way to draw k-partite graphs

(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.

-
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)$:

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 ) \; )$$

-

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?

-
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