Checking for outerplanarity in graph using BOOST?

Question

I just conceptualy want to know how to check if a graph is outerplanar or not. I know you can check for planarity in graph using BOOST, how do you check for outerplanarity? hints?

Answer 1

Perhaps a bit too late to answer, but I hope this will still help you or anyone else stumbling upon this question.

To this day Boost still doesn't have any outerplanarity testing algorithm implemented, but it's actually quite simple to check for outerplanarity using Boost's planarity checks.

According to Manfred Wiegers' Recognizing outerplanar graphs in linear time article:

a graph G is outerplanar iff K₁ + G (a new vertex is joined with all vertices of G) is planar.

So you need to add an additional vertex to the graph with edges connecting it to all vertices of the original graph and then check if the new graph is planar. If so, then the original graph is outerplanar.

Also note that each outerplanar graph with n vertices has less than 2n − 3 edges. Adding this edge count check could quickly filter out many obviously non-outerplanar graphs.