This is crossposted in cs.stackexchange.com, but I have been trying to use Mathematica do this and figured it might be more appropriate to ask here.

Define a "simple zonotope" to be a regular $2n$-gon which is tiled by the following rule: all tiles are rhombi. They key point here is that rhombuses have equal side lengths (say equal to 1), but their shapes are allowed to vary arbitrarly. Here's an example of a 12-gon zonotope:

There are many characterizations and properties of these objects. For example, one can encode a zonotope using $2n$ vectors (one for each outer edge) since we can just translate copies of each vector.

What I would like to do is the following: I have the adjacency matrix of a graph that I believe to be a simple zonotope. Specifically, you can assume that we are starting with a planer geometric graph, in that I have an adjacency matrix, in addition to having (x,y) coordinates of each point. In other words, it's fairly straightforward to identify which vertices go to the outer vertices of the $2n$-polygon.Here's an example of a geometric graph that I could have:

In the above picture, the two red vertices indicate the north/south poles of the zonotope they are mapped to (which happens to be the zonotope in the first picture).

Question: What is the most painless way of drawing the simple zonotope from a given adjacency matrix plus geometric graph coordinates?

Some observations: part of the algorithm is somewhat clear to me: one should work from the outside in. Once a specific rhombus side has been identified, all sides below it must be the same until we run into the opposite side of the zonotope. However this all seems very computationally expensive. I am honestly not preferential to any specific solution. I would even accept something akin to attaching springs to vertices and then running the algorithm until the graph converges to a zonotope.

What I have tried in Mathematica 8.0:

I've been trying to use

GraphPlot[A, VertexCoordinateRules -> VertexCycleCoordTag, VertexLabeling -> True,
Method -> {"SpringElectricalEmbedding", "RepulsiveForcePower" -> -2}]


Here 'A' is the adjacency matrix (in this case a 22x22 matrix). 'VertexCycleCoordTag' fixes what I know to be the outer vertices of this particular adjacency matrix. Here is the output:

Not too shabby! The repulsive force helped organize things here a bit. However, I would ideally like to fix the edge lengths to all be equal and to start seeing rhombi. I've had trouble doing this, even after consulting a post talking about EdgeWeight. It doesn't seem like GraphPlot has the EdgeWeight option (is this amended in Mathematica 9.0?).

Here's the full code, where 'VertexCycle' denotes the vertices which run around the edge of the 2-n gon in counterclockwise order:

A={{0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1}, {0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1}, {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1}, {1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0}, {1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0,
0}, {0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0,
0}, {0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0}, {0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0,
0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0,
0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1,
0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1,
0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1,
0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0,
0}, {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0}};

VertexCycle={21, 18, 15, 9, 4, 1, 22, 3, 8, 14, 17, 20};

n = Length[VertexCycle]/2;
VertexAngles[{x_, y_}] := {x*Cos[Pi/n] - y*Sin[Pi/n],
x*Sin[Pi/n] + y*Cos[Pi/n]}

VertexCycleCoordTag = {};
For[i = 1, i < 2*n + 1, i++,
VertexCycleCoordTag =
Append[VertexCycleCoordTag,
VertexCycle[[i]] -> VertexCycleCoord[[i]]]];

GraphPlot[A, VertexCoordinateRules -> VertexCycleCoordTag,
VertexLabeling -> True,
Method -> {"SpringElectricalEmbedding", "RepulsiveForcePower" -> -2}]

-
If you have the (x,y) coordinates already, why not use those in locating your graph vertices? –  Daniel Lichtblau Aug 3 '13 at 19:57
@Daniel Lichtblau: I have the $(x,y)$ coordinates of all points for the geometric graph which allows me to identify the boundary and more or less where the regions go. It's not clear however how to efficiently determine the angles in the rhombi of the zonotope that corresponds to the geometric graph. Right now I'm just hoping Mathematica has a built in function that can arrange and scale everything properly. In other words I'm hoping that fixing edge lengths to be equal will force it to draw a zonotope –  Alex R. Aug 3 '13 at 20:25
I would like this to be possible, but I'm not convinced. After all, it's easy to make a weighted graph that can't be drawn accurately in 2 dimensions (Graph[{1 <-> 2, 2 <-> 3, 3 <-> 1}, EdgeLabels -> "EdgeWeight", EdgeWeight -> {1, 42, -8}]) presumably Mathematica puts topology before accuracy? –  cormullion Aug 3 '13 at 21:44

Using your A:

a = A /. 0 -> Infinity;

WeightedAdjacencyGraph[a, EdgeLabels -> "EdgeWeight",