6
$\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.

Improve this question
$\endgroup$
2
  • $\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, 2014 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, 2014 at 11:09

2 Answers 2

Reset to default
12
$\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.

Improve this answer
$\endgroup$
7
  • 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, 2014 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, 2014 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, 2014 at 11:11
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Rotation_system $\endgroup$
    – Tony Huynh
    Oct 29, 2014 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, 2014 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.

Improve this answer
$\endgroup$
2
  • 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, 2014 at 11:50
  • $\begingroup$ "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. " Could you provide a reference to support that claim? $\endgroup$
    – Stef
    Dec 27, 2021 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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