MIP formulation for graph planarity test
MIP formulation for graph planarity test
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 (
); but this depends on how the nodes (and edges) are organized in space, which is not part of the input data. planar ; 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.
K2-Think
To determine if a graph is planar using Mixed Integer Programming (MIP), we can model the problem as a feasibility check for the existence of a Kuratowski subdivision (either (K_5) or (K_{3,3})). A graph is non-planar if and only if it contains a subdivision of (K_5) (complete graph on 5 vertices) or (K_{3,3}) (complete bipartite graph on 3+3 vertices). Below is a high-level MIP formulatio...
GPT-5
Yes. There are several mixed‑integer programming formulations that decide planarity. Two practically useful ways are:
A. As a maximum planar subgraph (MPS) ILP with Kuratowski cuts (branch‑and‑cut)
Idea:
- Introduce a binary variable x_e for each edge e ∈ E indicating whether e is kept.
- Maximize the number of kept edges. A graph is planar iff you can keep all edges.
Model:
- Variables: x_e ∈ ...
Claude Opus 4
This is indeed a fascinating modeling challenge. While I don't have a complete MIP formulation ready, I can outline some approaches that could potentially lead to one:
Potential MIP Approaches
1. Kuratowski's Theorem Approach
Since a graph is planar if and only if it contains no subdivision of K₅ or K₃,₃, we could formulate:
Variables:
- Binary variables indicating whether certain s...
o3 Pro
Yes, you can decide planarity with a Mixed-Integer Programming (MIP) model.
Below are two independent formulations.
- “Certificate of planarity’’ : look for a straight–line grid drawing
By Fáry’s theorem every planar graph on n vertices admits a straight-li...
DeepSeek R1
One common approach is to use the concept of an "...
o4 mini
Below is one way to turn the existence of a straight‐line planar drawing into a (pure) MILP. It is purely “warm-up” in the sense that it is neither small nor pretty, but it is completely elementary and of polynomial size in |V|,|E|.
- Decision variables
• For each vertex v∈V two integer coordinates
x_v,y_v ∈ {0,1,…,N}, N:=|V|.
• For eac...
o3
Below is a completely explicit MILP that decides whether an (undirected, simple) graph G=(V ,E ) is planar.
If the model is feasible it returns a combinatorial embedding – an ordering of the incident edges around every
vertex – that is a certificate of planarity;
if it is infeasible the graph is non–planar.
(The formulation is polynomial in |E| and |V| ; it is therefore only a
theoretica...
Gemini 2.5 Pro
Excellent question that delves into the expressive power of Mixed-Integer Programming. The answer is yes, it is possible to create a MIP formulation to test for graph planarity, but it is a complex modeling exercise and would be vastly less efficient than specialized algorithms.
The key is to move away from the geometric definition (x,y coordinates) which leads to non-linear constraints, and ...
Claude 3.7 Sonnet
MIP Formulation for Graph Planarity Testing
Testing whether a graph is planar (can be drawn in a plane with no crossing edges) is a fundamental problem in graph theory. While polynomial-time algorithms exist for this purpose, formulating it as a Mixed Integer Program (MIP) presents significant challenges.
Why This Problem Is Difficult
A direct MIP formulation for planarity testing is chall...
You need to be logged in to submit an answer