Planar face traversal

[kylevansice]

Are there any examples of how to use planar face traversal?

[OndrejNepozitek]

Hey! Can you please tell me what do you want to achieve? Is it not enough for you to get the planar embedding of a given graph?

The reason I implemented this algorithm is that I needed it written in C# so I could use it in different library. So it isn't really well documented and probably doesn't provide any advanced features.

[kylevansice]

Thanks for the response! I want to achieve something similar to the Planar Face Traversal available in the Boost C++ graph library, in C#. Essentially I want to find all the faces of the graph.

https://www.boost.org/doc/libs/1_51_0/libs/graph/doc/planar_face_traversal.html

[OndrejNepozitek]

Well, then you don't need to use the Planar Face traversal at all.

Just do something like this:

var boyerMyrvold = new BoyerMyrvold<int>();
var graph = // construct graph e.g. with new UndirectedAdjacencyListGraph<int>()
var isPlanar = boyerMyrvold.TryGetPlanarFaces(graph, out var planarFaces);

If the graph is planar, then planarFaces.Faces contains all the faces of a planar embedding of the graph - which should be exactly what you're looking for.

[kylevansice]

Amazing! It works well for me. One last question though, once I have the faces, how do I extract the edge and vertex indices that belong to each? Below is my code so far.

var boyerMyrvold = new GraphPlanarityTesting.PlanarityTesting.BoyerMyrvold.BoyerMyrvold<int>();
var graph = new GraphPlanarityTesting.Graphs.DataStructures.UndirectedAdjacencyListGraph<int>();
int [] testVertices = new int [] {0,1,2,3,4,5, 6,7};

for(int i = 0;i < testVertices.Length;i++){
  graph.AddVertex(testVertices[i]);
}

graph.AddEdge(0, 1);
graph.AddEdge(1, 2);
graph.AddEdge(2, 3);
graph.AddEdge(3, 0);
graph.AddEdge(3, 5);
graph.AddEdge(5, 4);
graph.AddEdge(4, 2);
graph.AddEdge(5, 7);
graph.AddEdge(7, 6);
graph.AddEdge(6, 3);

GraphPlanarityTesting.PlanarityTesting.BoyerMyrvold.PlanarFaces<int> planarFaces;
boyerMyrvold.TryGetPlanarFaces(graph, out planarFaces);

A = planarFaces.Faces.Count;

[OndrejNepozitek]

If you want to get all the vertices on a single face, you can do something like this:

var planarFaces = // get planar faces as in your code above

foreach (var face in planarFaces.Faces) {
    var vertices = face.Distinct(); // Each face is a list of ints
}

Note that on each face, some vertices may appear multiple times. So it's important to get only the distinct values if you are interested only in which vertices are on the face and not in the actual order of vertices on the face.

If you want to get all the edges that are on the face, you can utilize the fact that the vertices are in the same order as they appear on the face.

var planarFaces = // get planar faces as in your code above

foreach (var face in planarFaces.Faces) {
    var edges = new List<Tuple<int, int>>();

    for (var i = 0; i < face.Count; i++) {
       edges.Add(Tuple.Create(face[i], face[(i + 1) % face.Count)]; // The modulo operation is here so that we can simply connect the last vertex with the first one
    }

    // Make sure to handle possible corner cases like a face with one or two vertices, etc.
}

P.S.: I didn't test the code so it's quite possible that there are some errors.

[kylevansice]

Thanks, this is super helpful! Unfortunately, I'm getting a couple errors that I can't sort out. When trying to get the vertices, I get the following error in the foreach loop...

1. Error (CS1579): foreach statement cannot operate on variables of type 'GraphPlanarityTesting.PlanarityTesting.BoyerMyrvold.PlanarFaces' because 'GraphPlanarityTesting.PlanarityTesting.BoyerMyrvold.PlanarFaces' does not contain a public definition for 'GetEnumerator' (line 83)

and when I try to loop through all the faces, it returns that no method called distinct exists....

2. Error (CS1061): 'System.Collections.Generic.List' does not contain a definition for 'Distinct' and no extension method 'Distinct' accepting a first argument of type 'System.Collections.Generic.List' could be found (are you missing a using directive or an assembly reference?) (line 89)

Code below....

var boyerMyrvold = new GraphPlanarityTesting.PlanarityTesting.BoyerMyrvold.BoyerMyrvold<int>();
var graph = new GraphPlanarityTesting.Graphs.DataStructures.UndirectedAdjacencyListGraph<int>();
int [] testVertices = new int [] {0,1,2,3,4,5, 6,7};

for(int i = 0;i < testVertices.Length;i++){
  graph.AddVertex(testVertices[i]);
}

graph.AddEdge(0, 1);
graph.AddEdge(1, 2);
graph.AddEdge(2, 3);
graph.AddEdge(3, 0);
graph.AddEdge(3, 5);
graph.AddEdge(5, 4);
graph.AddEdge(4, 2);
graph.AddEdge(5, 7);
graph.AddEdge(7, 6);
graph.AddEdge(6, 3);

GraphPlanarityTesting.PlanarityTesting.BoyerMyrvold.PlanarFaces<int> planarFaces;
boyerMyrvold.TryGetPlanarFaces(graph, out planarFaces);
GraphPlanarityTesting.PlanarityTesting.BoyerMyrvold.PlanarEmbedding<int> planarEmbedding;

int [] vertices;

foreach(var face in planarFaces){

}

for(int i = 0;i < planarFaces.Faces.Count;i++){
  vertices = planarFaces.Faces[i].Distinct();
}

And thanks very much for all your help!

[OndrejNepozitek]

Here is the whole code: https://gist.github.com/OndrejNepozitek/0b4a6aa5f9fe0976bce14d185a93d5f3

[kylevansice]

Thanks for all the help! It turns out I wasn't linking in Linq properly.

I'm able to extract the vertices now, but I'm noticing a problem when faces occur inside others, see below. Any thoughts?

[OndrejNepozitek]

It's probably because planar embedding are not unique. There may be multiple ways how to draw a planar graph so the result of the algorithm can be different from your drawing.

On your top right picture, if you draw the vertex 6 inside the face 2 3 4 5, you'll probably get the same embedding as the algorithm returns.

[kylevansice]

Ok, thanks again for all the help! I need to find the faces as drawn though... let me know if you have any suggestions on achieving that.

[OndrejNepozitek]

If you want to get the faces from a given planar embedding (your drawing) then you have to somehow provide information about the drawing to the algorithm, not just create the input graph. As I said before - one graph can have multiple planar embeddings (and therefore multiple possible sets of faces).

One possible way of doing that is to represent the drawing as a set of vertices and for each vertex, provide a list of edges around that vertex in a clockwise order. So your input would look something like this:

• vertex 1, edges 2, 4, 0 (vertex 1 neighbors with vertices 2, 4 and 0)
• vertex 2, edges 3, 5, 1
• vertex 3, edges 0, 4, 2
• etc..

With such an input, the planar face traversal can be used to compute the faces of your drawing. But it all depends whether you're able to convert your drawing to the representation mentioned above.