<p><strong>Q:</strong> Is there an <em>efficient</em> (I)LP formulation of planarity?</p>
<p>More specifically, I am looking for a set of constraints that are satisfied by exactly all planar graphs on <span class="math-container">$n$</span> vertices, in order to optimize some linear objective function over these graphs, e.g. fractional chromatic number. (Actually, over graphs that are the union of two planar graphs, but this should be similar.)</p>
<p>My first approach was to use variables of the <span class="math-container">$x$</span> coordinate and the <span class="math-container">$y$</span> coordinate of each vertex,
and then use a geometric approach to determine whether two edges are crossing.
However, this requires roughly <span class="math-container">$O(n^4)$</span> constraints, which might become intractable very quickly.</p>
<p>My second approach was to use the fact that there are at most <span class="math-container">$3n-6$</span> edges in a planar graph.
We can then assign to each edge two variables corresponding to the vertices that are their endpoints.
Then, checking for pairwise intersection only requires <span class="math-container">$O(n^2)$</span> constraints.</p>
<p>The two approaches above are integer LP, however planarity can be checked in polynomial time, therefore
one could hope that there is a linear programming formulation, which might lead to a faster resolution.</p>
<p>Wagner's or Kuratowski's theorem may yield efficient formulations, but I wasn't able to come up with one.</p>
<p>Finally, I could not find articles that use a linear program formulation of planarity -- did I miss any?</p>

CC BY-SA 4.0
2020-12-28T19:36:20.953Z
If you had such an LP wouldn't you be able to solve the NP-Hard maximum  (weight) planar subgraph problem?
Chandra Chekuri
CC BY-SA 4.0
2020-12-28T21:06:46.323Z
I'm confused: what are the variables, and what is fixed?  Are the vertices at fixed locations and the variables represent which edges are in the graph?  Are the vertices at variable locations?  What precisely do you mean by  "an efficient (I)LP formulation"?  I'd consider your second approach to qualify as an efficient ILP formulation, so I'm not sure what your requirements are.
D.W.
CC BY-SA 4.0
2020-12-29T21:32:36.153Z
I think OP is asking for an extended formulation of planar graphs on $n$ vertices.
Turbo
<linear-programming><planar-graphs><integer-programming>
(Integer) Linear Program formulation of planarity?
GBathie
# (Integer) Linear Program formulation of planarity?

(Asked by: username_0 on 2020-12-28)

**Q:** Is there an *efficient* (I)LP formulation of planarity?

More specifically, I am looking for a set of constraints that are satisfied by exactly all planar graphs on $n$ vertices, in order to optimize some linear objective function over these graphs, e.g. fractional chromatic number. (Actually, over graphs that are the union of two planar graphs, but this should be similar.)

My first approach was to use variables of the $x$ coordinate and the $y$ coordinate of each vertex,
and then use a geometric approach to determine whether two edges are crossing.
However, this requires roughly $O(n^4)$ constraints, which might become intractable very quickly.

My second approach was to use the fact that there are at most $3n-6$ edges in a planar graph.
We can then assign to each edge two variables corresponding to the vertices that are their endpoints.
Then, checking for pairwise intersection only requires $O(n^2)$ constraints.

The two approaches above are integer LP, however planarity can be checked in polynomial time, therefore
one could hope that there is a linear programming formulation, which might lead to a faster resolution.

Wagner's or Kuratowski's theorem may yield efficient formulations, but I wasn't able to come up with one.

Finally, I could not find articles that use a linear program formulation of planarity -- did I miss any?

**Tags:** linear-programming, planar-graphs, integer-programming

> **Comments:**
> **username_1**: If you had such an LP wouldn't you be able to solve the NP-Hard maximum  (weight) planar subgraph problem?  
> **username_2**: I'm confused: what are the variables, and what is fixed?  Are the vertices at fixed locations and the variables represent which edges are in the graph?  Are the vertices at variable locations?  What precisely do you mean by  "an efficient (I)LP formulation"?  I'd consider your second approach to qualify as an efficient ILP formulation, so I'm not sure what your requirements are.  
> **username_3**: I think OP is asking for an extended formulation of planar graphs on $n$ vertices.  

---

## 0 answers

