7

In this question, it was asked wether a MIP formulation exists to test for a graph's planarity. The inputs are the graph's nodes and edges, and the output would be a certificate which guarantees that the graph is, or is not, planar.

The python package NetworkX provides a method which does exactly this, but it is not based on linear programming. The source code provides the following references:

  • Ulrik Brandes: The Left-Right Planarity Test (2009)
  • Takao Nishizeki, Md Saidur Rahman: Planar graph drawing, Lecture Notes Series on Computing: Volume 12 (2004)

Some ideas:

  • Euler's theorem ($n-m+f=2$); but this depends on how the nodes (and edges) are organized in space, which is not part of the input data.
  • $G$ planar $\implies m\le 3n-6$; but this does not cover all cases, it can be a tool to prove that a graph is not planar, but is useless the otherway around.
  • There is a relationship between planar graphs and book embeddings (see this great video from Numberphile for a recent breakthrough in graph theory on the subject), but not sure it helps.
  • Other characterizations of planar graphs are mentioned on the Wikipedia page, such as Whitney's planarity criterion or Mac Lane's planarity criterion. These might be interesting.

To this day, the question has not been answered. I find the question interesting from a modeling point of view and am curious wheter it can be answered with a MIP.

Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • My best bet would be that you can check if the graph has $K_5$ or $K_{3,3}$ as a minor, which is equivalent to planarity by Wagner's theorem. Checking if $H$ is a minor of $G$, for fixed $H$, seems doable, you have to find $|V(H)|$ vertex-disjoint connected subgraphs in $G$, each representing a vertex of $H$, such that there is at least one edge between parts corresponding to adjacent vertices of $H$. Disclaimer, I have not checked any details. – Michal Adamaszek May 01 '23 at 10:46
  • As far as I checked Euler's theorem, It is not correct for the space with dimension $\mathbb{R}^2$. As the graph was planar. (I am not aware of if there exists a counterpart). – A.Omidi May 01 '23 at 10:52

0 Answers0