11

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 generality we can assume that no two incident edges cross and that no two edges cross twice, for otherwise we can modify the drawing to eliminate these crossings ...


5

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: http://arxiv.org/abs/2009.12369) The paper presents a slightly more restricted variant, Monotone Planar 3-SAT with Neighboring Variable Pairs, which requires ...


2

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. This is because any pair of adjacent (cyclically) variables can be in a clause and that gives you very little freedom, you can only reorder them by a cyclical ...


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