5

You can in cubic time figure out which pair of edges to let cross. For this, try all $O(n^2)$ pairs, augment the graph by replacing the two edges by a degree 4 vertex (representing the crossing), and test for planarity in linear time. If you already know the two edges that cross, you can use standard techniques to draw the augmented (planar) graph with ...


3

Let $G=(V,E)$ be an arbitrary instance of $3$-coloring. Construct a new graph $G'=(V',E')$ as follows: $V'$ contains all the vertices in $V$, and for every edge $e\in E$ it contains a corresponding new vertex $x(e)$. $E'$ contains all the edges in $E$, and for every edge $e=\{u,v\}\in E$ it contains the two new edges $\{x(e),u\}$ and $\{x(e),v\}$. Note the ...


3

Even computing a maximum independent set of unit axis-parallel squares is known to be np-hard: https://www.sciencedirect.com/science/article/pii/0020019081901113?via%3Dihub Since coloring is a "harder" problem, it should also be NP-hard. A constant approximation follows as if a point is covered by $k$ squares, then the chromatic number is at least $...


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