Probability

Graph Theory

Planar Graphs

         

Is this graph planar?

Is this graph planar?

Suppose a graph GG is not planar. If we add an edge to GG to connect two previously disconnected nodes to create the graph GG', is GG' planar?

Suppose that there are three houses A,B,CA, B, C 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 K3,3K_{3,3} is a planar graph.

Suppose GG is a planar graph. If we create GG' by adding a single edge to GG, is GG' planar?

×

Problem Loading...

Note Loading...

Set Loading...