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:
- 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.
- 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!