Planar Embedding (Planar Face Traversal) Algorithm in C#

Question

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.

Graviton · Accepted Answer · 2010-12-05 07:15:48Z

0

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.

answered Dec 5, 2010 at 7:15

Graviton

83.2k150 gold badges443 silver badges614 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Adam White · Accepted Answer · 2022-05-29 16:49:57Z

0

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

It appears to use 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

answered Oct 29, 2021 at 14:31

Adam White

3,4181 gold badge25 silver badges20 bronze badges