12
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 ...
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:...
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. ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
graph-drawing × 19graph-theory × 11
cg.comp-geom × 8
graph-algorithms × 6
planar-graphs × 4
co.combinatorics × 3
reference-request × 2
software × 2
ds.algorithms × 1
np-hardness × 1
optimization × 1
soft-question × 1
ds.data-structures × 1
machine-learning × 1
sat × 1
big-list × 1
directed-acyclic-graph × 1
ai.artificial-intel × 1
data-streams × 1
writing × 1
binary-trees × 1