# Tag Info

## Hot answers tagged graph-drawing

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 ...
• 50.2k
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:...
• 141