Un graphe est constitué de points reliés entre eux par des arêtes. Un graphe étant donné, on cherche la façon de le représenter en utilisant le moins possible de croisements entre ses arêtes.
Les auteurs travaillent sur la représentation d’un graphe avec un nombre minimum de croisements entre les arêtes. Ils s’intéressent plus particulièrement aux graphes complets où, en considérant le nombre de sommets, le nombre d’arêtes et le nombre de régions, ils donnent une borne inférieure du nombre minimal de croisements en fonction du nombre de sommets. Enfin ils s’intéressent aux graphes bipartis où ils montrent qu’il est impossible de relier trois maisons à trois sources (eau, gaz et électricité) sans que les connections se croisent. Ils donnent en fin d’article une conjecture intéressante sur la représentation optimale en termes de nombre de croisements d’un graphe biparti.
Les auteurs travaillent sur la représentation d’un graphe avec un nombre minimum de croisements entre les arêtes. Ils s’intéressent plus particulièrement aux graphes complets où, en considérant le nombre de sommets, le nombre d’arêtes et le nombre de régions, ils donnent une borne inférieure du nombre minimal de croisements en fonction du nombre de sommets. Enfin ils s’intéressent aux graphes bipartis où ils montrent qu’il est impossible de relier trois maisons à trois sources (eau, gaz et électricité) sans que les connections se croisent. Ils donnent en fin d’article une conjecture intéressante sur la représentation optimale en termes de nombre de croisements d’un graphe biparti.