Is this graph planar?
Is this graph planar?
Suppose a graph is not planar. If we add an edge to to connect two previously disconnected nodes to create the graph , is planar?
Suppose that there are three houses and three utilities 1, 2, and 3 each of which needs to be connected by a wire to all three houses. Assuming the utilities and the houses are all points (nodes), is there a way to position them and the wires (edges) such that no two wires overlap?
Note: this is the same as asking whether is a planar graph.
Suppose is a planar graph. If we create by adding a single edge to , is planar?