Enumerating all non-planar embeddings of a generic connected graph in the plane

Question

Hi There

I've been tackling a problem in computer science, which relies quite heavily on graph theoretic concepts. I'd appreciate it if anybody could provide insight into how to enumerate all non-planar embeddings of a generic connected graph in the plane.

Assume we are given an undirected connected graph $G=(V,E)$ with straight edges, $n$ nodes, and a symmetric distance matrix $D$ of size $n \times n$ that weights the edges in $E$. The weight is simply the straight line Euclidean distance between the two vertices in the corresponding edge.

The 2D Graph Realization problem seeks to find a non-planar (edges may cross) embedding of $V$ in the plane, such that the measured distances are "as close to" the observed distances $D$. In general, this problem is NP-Hard. However, if we ignore degenerate cases in which there is an algebraic relation between vertices (three or more vertices are collinear) the problem becomes tractable. From here on we will assume generality.

Depending on the number and configuration of edges that are known, the embedding may not be unique. The certification problem seeks to determine whether it is impossible to find a unique embedding, given the edges that are known. One is able to certify the uniqueness of an embedding in the plane using graph rigidity theory. (Jackson and Jordan,2005) proved that a graph has a unique embedding in the plane if and only if it is redundantly rigid and triconnected. The first condition relies on a concept known as Generic Rigidity, and it can be tested with the 2D Pebble Game proposed by (Hendrikson, 1992). The second condition can be tested by building a SPQR tree (Hopcraft and Tarjan, 1973).

(Mutzel and Weiskircher, 1999) showed how to enumerate all combinatorial planar embeddings of a biconnected graph using an SPQR-tree. This is the closest result that I can find to my problem. However, my problem differs in the following two ways:

1. A planar graph has the distinct property that edges only intersect at the vertices. I'm looking to find a way of optimizing over combinatorial non-planar embeddings of a graph.
2. Their model assumes that the graph is biconnected. I'd prefer to drop this assumption in favour of connectedness.

So far, I've thought of the following crude algorithm to achieve what I'm looking for. It begins by using the 2D pebble game to find all generically rigid clusters in a given graph. These clusters are rigid against small continuous forces, but may move relative to one another. I then parameterise the K degrees of freedom with real angles $r_1 \ldots r_K$. For clusters with greater than 4 nodes I have to also parameterise the possible reflections. In order to do this I obtain an SPQR tree for each cluster, assuming that generic rigidity implies biconnectivity (a requirement of the SPQR tree data structure). The P-nodes in the SPQR tree indicate where reflection is possible, and I encode all L possible reflections with binary variables $b_1 \ldots b_L$. The space of possible embeddings of the graph is given by $b_1 \ldots b_L$ and $r_1 \ldots r_K$. I the perform some optimization algorithm over this search space.

Does this appear to be a reasonable approach, or am I making any problematic assumptions? Any comments or extra information would help me greatly!

Answer 1

As I mentioned in my comment, there are two kinds of problems here:

• If the graph is generically rigid, this is an enumeration problem, and quite a hard one.
• If the graph is generically flexible, then this is a question of the configuration space of the framework.

For the rigid case, I'm not aware of a better exact answer than doing something based on Groebner basis computations, which will, in general, be very slow. I assume that some formal negative results about framework realizability (e.g., Owen and Power http://www.ams.org/journals/tran/2007-359-05/S0002-9947-06-04049-9/) translate to enumeration if you're given one realization, but I can't think of a reference.

There is, however, a lot of heuristic work in this area. For example, Meera Sitharam has a method based on hierarchical decompositions that's in the spirit of what you want (http://www.cise.ufl.edu/~sitharam/skeleton.pdf). It seems like you're not interested in realizability only, but if the graph is globally rigid and you can take multiple measurements, there is a nice method due to Zhu, Gortler, and Thurston (http://dl.acm.org/citation.cfm?id=1921630).