There is a unique path from any corner to another by following the arrows. You can go in the direction of the arrows or if there is a circle on a corner you can stay still

The following is a convex polyhedron with edges labeled such that there is a unique length 2 path from any corner to another by following the arrows. You can go in the direction of the arrows or if there is a circle on a corner you can stay still

If this circle bit upsets you there is a fairly simple proof that any directed graph with n vertices and with a unique distance 2 path between any 2 points must have at exactly sqrt(n) loops so this is unavoidable

This property is vaguely interesting as this means that sqrt(n) must be an integer, for 4 corners we can do a square and for 9 we can do this Tri-Augmented Triangular Prism, i would conjecture that there are no other convex shapes with this property but i dont have a proof right now. The construction that gives this graph for n=9 gives a square for n=4 and non-planar graphs for 9<n<1226 so presumably they are never planar beyond this point so cannot be made into shapes, I have now proven this to be true, the only planar examples are for n=1,4,9

We can also derive that there if there is n^2 corners there have to be n arrows pointing in and n pointing out of each corner (this bit is harder to see)

The actual maths is as follows. If we let A be the adjacancy matrix of the graph we are looking for a matrix whos entries are positive integers and who squares to the matrix of all ones

Since the matrix of all ones has eigenvalues of 0,...,0,n, A must have eigenvalues of 0,...,0,±sqrt(n). The number of loops is then the trace which is the sum of these values

so since the trace is a positive integer its sqrt(n) which must be an integer

By noting that (A^2)^2 = nA^2 we see that A^2(A^2-n)=0 so letting m^2 = n, A^2(A-m)(A+m)=0, we also see that the characteristic polynomial of A is A^{n-1}(A-m) since we know the eigenvalues

So the minimal polynomial must divide both of these polynomials so must divide A^2(A-m) (in fact if n=/=1 this is the minimal polynomial since A^2=/=0 clearly and A(A-m)=/=0 as A^2 has only ones but Am has only m's) so A^2A=A^2m. Since each entry of A^2A will give you the sum over a column we see that the sum over each column is m

So there is m arrows pointing out of any vertex, also since (A^t)^2 = (A^2)^t = A^2 the same applies to the rows so there is m arrows pointing into each vertex too

We can see an example construction by taking the matrix S that is the mxm identity with the rows cycled along one place then taking the block matrix A = [[S^0, S^1, S^2 ... S^{m-1}],[S^0, S^1, S^2 ... S^{m-1}]...[S^0, S^1, S^2 ... S^{m-1}]]

Then since the sum of S^m is the matrix of all 1s we get that this matrix squared is what we want

After some additional thinking we can conclude that the only planar examples are at n=1,4,9. Since if the graph were planar then there would be a vertex of degree <6 and we can show that there isnt

Since there is a unique path of length 2 from each vertex to itself we see that each vertex either has exactly one bidirectional edge or loop, since we know how many ins and outs there are already we can conclude

Not taking this into account the degree is 2m, if there's a bidirectional edge then its just 2m-1 as we don't count it twice,if there's a loop then I cant remember if we count it or not, for safety however ill remove it giving degree equal to 2m-2. So we need 2m-2<6, so m<4 so we cant get any bigger shapes and we're done

The code for checking planarity is

Additionally we can find examples for other powers with the following genetic algorithm