The IsPlanar command returns true if the graph is planar and false otherwise. If a name such as faces is specified, then this name is assigned the set of lists of the vertices of each face of the graph. The strategy is to use an algorithm by Demoucron, etc. (see Algorithmic Graph Theory by Alan Gibbons).

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{SpecialGraphs}\right)\:$

$\mathrm{K4}≔\mathrm{CompleteGraph}\left(4\right)$

$\mathrm{K4}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 4\; vertices\; and\; 6\; edge(s)}$

$\mathrm{IsPlanar}\left(\mathrm{K4}\,'F'\right)$

$\mathrm{true}$

$F$

$\left[\left[3\,1\,2\right]\,\left[2\,1\,4\right]\,\left[3\,2\,4\right]\,\left[4\,1\,3\right]\right]$

$\mathrm{DrawGraph}\left(\mathrm{K4}\right)$

$\mathrm{NumberOfVertices}\left(\mathrm{K4}\right)-\mathrm{NumberOfEdges}\left(\mathrm{K4}\right)+\mathrm{nops}\left(F\right)-\mathrm{nops}\left(\mathrm{ConnectedComponents}\left(\mathrm{K4}\right)\right)-1$

$0$

$P≔\mathrm{PetersenGraph}\left(\right)$

$P≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edge(s)}$

$\mathrm{IsPlanar}\left(P\right)$

$\mathrm{false}$

$\mathrm{DrawGraph}\left(P\right)$