Pourquoi le graphique à l'intérieur de Graham Scan est-il toujours planaire

Question

L'une des façons de prouver que Graham Scan construit la coque convexe en temps linéaire est d'utiliser la planarité du graphique obtenu en exécutant l'algorithme. Ce graphique est toujours planaire, donc selon la formule d'Euler, le nombre d'arêtes ne peut jamais être supérieur à 3 $ * n $ (où $ n $ est le nombre de sommets). Ma question est, comment savons-nous que les bords examinés par Graham Scan ne se croisent jamais (donc forment toujours un graphique plane)? Voici la capture d'écran de ceci qui est discutée dans le cours "Géométrie informatique" de l'Université Tsinghua (d'Edx.org). Le conférencier vient de mentionner que c'était vrai, mais n'a pas donné la preuve.