Add an edge to a graph without becoming nonplanar

Question

This is an attempt to generate numbers in the sequence A000109, where efficiency is not necessary

(Yes, this is yet another help question for the OEIS sequences :P)

One of the methods of calculating the sequence as stated in the description is:

simple planar graphs with 3n-6 edges

Generating simple graphs with a set number of edges is easy (though not necessarily efficient using my algorithm). To solve this challenge, I have a question:

What is the easiest / most efficient (I favor easy implementation over efficiency for this purpose) way to determine if adding an edge to a planar graph will cause it to become non-planar?

I have searched over Math.SE and through the papers in the OEIS links but did not find the exact linear-time algorithm for planarity checking.

Any help would be appreciated. Thanks!

Answer 1

The approach you're taking is much more complicated than the easiest approach to generating the graphs counted by A000109. So if you don't mind, I'll give you an easy-to-implement way to generate those graphs, rather than an easy-to-implement way to check for planarity (which I'm not sure exists, even in the case where we're just adding one edge to a planar graph).

In the paper Fast generation of planar graphs (G. Brinkmann and Brendan McKay), Figure 4 and the example at the bottom of page 4 together give an easy-to-implement way to eventually generate all planar triangulations on at least $4$ vertices. Here's a summary of how it works.

We define the following three operations that turn an $n$-vertex planar triangulation into an $(n+1)$-vertex one:

1. Pick a $3$-cycle in the graph and add a new vertex adjacent to all its vertices.
2. Pick two adjacent $3$-cycles in the graph (sharing an edge). Delete their common edge to make a $4$-cycle and add a new vertex adjacent to all its vertices.
3. Pick three $3$-cycles $C_1, C_2, C_3$ such that $C_1$ and $C_2$ share an edge and $C_2$ and $C_3$ share a different edge. Delete their common edge to make a $5$-cycle and add a new vertex adjacent to all its vertices.

The claim in the paper is that, if you start from all the $n$-vertex planar triangulations and just apply these operations to all of them in all possible ways, you get all the $(n+1)$-vertex planar triangulations. This is probably easier to implement than any test for planarity.

(You might want to look into doubly connected edge lists (DCELs) or some similar data structure for storing the planar graphs you're working with.)

You will get a lot of redundancy in your list of $(n+1)$-vertex planar triangulations. So you'll have to somehow check when two planar triangulations are isomorphic, and delete the redundant ones. But this is also easy to do if you don't mind inefficiency: for one thing, we could just check all possible bijections between the vertex sets. (A lot of the complexity in Brinkmann and McKay's actual algorithms is about dealing with this redundancy more efficiently.)

Answer 2

The Wikipedia page on planarity testing lists multiple algorithms.

Answer 3

What is the easiest / most efficient (I favor easy implementation over efficiency for this purpose) way to determine if adding an edge to a planar graph will cause it to become non-planar?

Assuming you are only considering simple undirected graphs then if you maintain a list of faces and the cycles of vertices bounding them. You can add an edge between any two non-adjacent vertices bounding the same face (and the new edge will bisect that face and sub-dividing it into two new faces) and the graph will still be planar.

Once all the faces of the graph have 3 edges then the graph will be a maximal planar graph (a.k.a. a triangular graph) and no further edges can be can be added without making the graph non-planar.