Planar Embedding (Planar Face Traversal) Algorithm in C#

0
votes

I have a graph G. The graph is a planar graph.

I wish to find all the faces of the graph. I understand that constructing a planar embedding is the way to find the faces ( or regions, or cycles), such that all the edges must be shared by at most 2 faces.

Is there a readily made implementation of planar embedding algorithm in C#? Either commercial or open source is fine.

2
c#graphplanar-graph

2 Answers

0
votes

After some searching, I found that Planar Face Traversal function in Boost library suits my needs.

One can then wrap the function in plain C manner and call it from C# via PInvoke.

0
votes

Here, this C# project says it was inspired by the Boost library, and says it supports:

  • Checks if a given undirected graph is planar or not
  • Computes planar embedding if a given graph is planar
  • Computes faces of a given planar embedding

It appears to us Boyer-Myrvold Planarity Testing:

  • Checks that if a graph is one big cycle, it is planar and there are exactly two faces in the embedding
  • Checks that if a random graph has more than 3n - 6 vertices, it is not planar

https://github.com/OndrejNepozitek/GraphPlanarityTesting