1
$\begingroup$

Is there a way to convert a nonplanar graph into a planar one, but instead of deleting edges, the only allowed action is to add nodes

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Logically , that is not Possible.

(Proof 1) Suppose there was a way to add nodes to convert $NP$ a Non-Planar graph into $P$ a Planar graph.
Draw $P$ on a Plane without crossings. Now "delete" the added nodes to get back $NP$ which will still be drawn on a Plane without crossings ! Hence $NP$ is itself a Planar graph !
Contradiction !

(Proof 2) Non-Planar graph has a subgraph which makes it Non-Planar. When we add nodes , that subgraph still Exists (the new graph still has the same subgraph) hence it will still be Non-Planar : We can never get a Planar graph with the addition of nodes.
The subgraphs which may make a given graph Non-Planar :
$K_5$ & $K_{3,3}$
https://en.wikipedia.org/wiki/Kuratowski's_theorem
https://en.wikipedia.org/wiki/Wagner's_theorem

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .