4
$\begingroup$

I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 shares edges with nodes 1 8 and 30. As the graph is undirected, graph[8] will also contain the value 3.

I want to find an algorithm that will find all of the faces of the graph (my graph-theoretical knowledge is limited, I am essentially looking for all of the cycles that don't contain a smaller cycle within them), and provide the path for the boundary of each of those faces (e.g. 1->5->9->3->1).

It is safe to assume that the graph I have is both planar and connected.

With limited knowledge of graph-theory concepts I'd like to avoid getting too lost halfway through implementation, so simplicity is probably more valuable than efficiency. That said, the algorithm must not be horribly inefficient.

$\endgroup$
  • $\begingroup$ @bof It would appear that they are arbitrarily ordered. The problem will involve eventually moving the nodes to avoid crossings between the edges $\endgroup$ – JMcPherson Oct 29 '14 at 9:31
  • 2
    $\begingroup$ Leaving aside the fact that there might be more than one "correct" answer (as Fredorico noted), you are asking about planar embedding. It is one of those problems which can be solved very quickly even for enormous graphs (thousands of vertices) but coding efficient methods and getting the program exactly right is quite a challenge. See en.wikipedia.org/wiki/Planarity_testing for a summary of the methods with references. I suggest you look for existing software rather than rolling your own. $\endgroup$ – Brendan McKay Oct 29 '14 at 11:09
8
$\begingroup$

What you ask for is an unsolvable problem, because it depends on the embedding of the graph in the plane (or space). Consider the following graphs:

     enter image description here      enter image description here

They are isomorphic, and described by the same node-edge incidence matrix, but you want different answers for them.

You need to specify a planar embedding (i.e., coordinates for the vertices) for this to work.

$\endgroup$
  • 3
    $\begingroup$ What if the neighbors of each vertex are listed in counterclockwise order, i.e., the neighbors of 1 are 2,5,4,3 on the left, and 2,5,3,4 on the right? I guess that's enough to determine the embedding, isn't it? $\endgroup$ – bof Oct 29 '14 at 9:31
  • 1
    $\begingroup$ @bof This seems to help, but only if one considers also the 'outside' of the graph as a face (i.e., 1265 in the graph in the left). Otherwise you can just put 3,4,5,2 in this order in the middle column to have a counterexample. Is this enough? I am not sure; intuitively, yes, but we'd probably need an answer from someone more knowledgeable than me in this field. $\endgroup$ – Federico Poloni Oct 29 '14 at 9:45
  • 1
    $\begingroup$ The cyclic order of edges at each vertex uniquely defines an embedding on a sphere. For the plane you have to additionally say which face is on the outside. $\endgroup$ – Brendan McKay Oct 29 '14 at 11:11
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Rotation_system $\endgroup$ – Tony Huynh Oct 29 '14 at 11:15
  • 5
    $\begingroup$ @BrendanMcKay A cyclic order at each vertex (ribbon graph structure) defines a unique embedding to a closed oriented surface; if we are lucky, this surface is a sphere. On the other hand, given a ribbon graph structure, the regions are immediate (as orbits of an appropriate group action); in particular, so is the Euler characteristic hence the genus of the surface containing the graph. Then, if this happens to be $S^2$, it's entirely up to us which region is to be called unbounded. $\endgroup$ – Alex Degtyarev Oct 29 '14 at 11:43
4
$\begingroup$

Expanding a bit on the comments to Federico's answer: If the neighbors of each vertex are listed in counterclockwise order, this defines an embedding on a surface, and if this information was obtained from a given planar embedding, this is the one you get back.

Essentially, for a given edge $(n_1,n_2)$ you can find one of the faces it borders (and, analogously, the other one by considering $(n_2,n_1)$ instead) by looking up $n_1$ in the list of $n_2$'s neighbors, finding the next one, say $n_3$, in the (cyclic) order, and continuing with $(n_2,n_3)$, and then $(n_3,n_4)$ etc until you return to $n_1$.

Note that the non-uniqueness is only an issue if $G$ is not $3$-edge-connected. If it is, even if the ordering at the nodes is not given, you should still have a unique embedding into the sphere (and into the plane, modulo choice of the outer face). Not sure how to find it, though.

$\endgroup$
  • 2
    $\begingroup$ Actually you need 3-vertex-connected in general. If there is a cut of one or two vertices you can turn over the graph on one side if it. $\endgroup$ – Brendan McKay Oct 30 '14 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.