New answers tagged graph-algorithms
6
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
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 $...
Top 50 recent answers are included
