11 votes
Accepted

Pathwidth of planarized drawing of $K_{3,n}$

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why. (1) Fix a drawing of $K_{3,n}$. Without loss of ...
user avatar
5 votes
Accepted

NP-hardness of a planar SAT variant

The following paper answers the question in the affirmative – the variant remains NP-hard using a reduction from Monotone Planar 3-SAT: http://epubs.siam.org/doi/abs/10.1137/1.9781611976465.105 (arXiv:...
user avatar
  • 141
2 votes

NP-hardness of a planar SAT variant

Below I show that reordering is not possible in any sense, so a new hardness proof from scratch is needed. It's not even possible to reorder just one side if you don't eliminate redundant cluases. ...
user avatar
  • 13.5k

Only top scored, non community-wiki answers of a minimum length are eligible