planarity code mishandles graphs with no edges (segfault) #4505
Description
We get random segfaults from the planarity code because it doesn't seem to handle graphs with no edges properly.
The segfaults occur in these lines from sage/graphs/planarity/graphEmbed.c
Jfirst = theGraph->G[I].link[1];
if (theGraph->G[Jfirst].type == EDGE_FORWARD)
{
/* Find the end of the forward edge list */
Jnext = Jfirst;
while (theGraph->G[Jnext].type == EDGE_FORWARD)
The problem is that when there are no edges, theGraph->G[I].link[1] is -1, Jfirst is -1. If the random value at theGraph->G[-1].type is 2 (EDGE_FORWARD), then the code in the if block is executed and we get a segfault when trying to access fields inside the if block.
For now, this patch skirts the issue by checking for the case of no edges explicitly before Boyer's code is called.
I am emailing John Boyer about this as well.
CC: @sagetrac-ekirkman @sagetrac-bober
Component: graph theory
Issue created by migration from https://trac.sagemath.org/ticket/4505