Représentation en treillis du graphe non orienté

Question

Dans quelles circonstances un graphe non orienté peut-il être représenté par points de treillis entiers en coordonnées cartésiennes? Particularités:

% Chaque point du graphique est mappé sur (x, y) sur la grille cartésienne où x et y sont des entiers.

% Deux points (x1, y1) et (x2, y2) sur la grille cartésienne sont "connecté" si abs (x1-x2) < = 1 et abs (y1-y2) < = 1. En d'autres termes, chaque point a 8 voisins.

% Deux points sur la représentation graphique cartésienne doivent être connectés s'il y a une limite entre ces deux points sur le graphique .

Exemples:

% K4: Tous les points sont reliés les uns aux autres.

 
12 
34 

% K2,2: 1 et 2 à la fois relier à la fois 3 et 4, mais il n'y a pas d'autres connexions .

 
3 
1 2 
4 

Puisque je ne peux pas trouver une représentation en treillis pour K3,2 Je devine que graphiques treillis sont capables d'un sous-ensemble de graphes planaires.

Même question pour les points de réseau 3D.

Answer 1

Ce graphe de type treillis est planaire puisque K5 et K3,3 ne peuvent pas être représentés. K5 puisque dans K1,5 il y a au moins une paire de nœuds (à partir de 5) qui ne sont pas connectés. K3,3 car il n'est pas possible de placer 3 points non connectés que des «cercles» intersectent sur plus d'un point.

C'est un sous-ensemble approprié de graphes planaires puisque K1,9 ne peut pas être représenté.

Pour le cas 3D, il n'est pas planaire puisque K5 peut être représenté, K4 à partir de 2D et un point au-dessus d'eux. Mais certains graphiques planaires ne peuvent pas être représentés, par ex. K1,28.