Squaregraph

Les graphes carrés incluent comme cas particuliers les arbres , les graphes de grille , les graphes d'engrenages et les graphes de polyominos .

En plus d'être des graphes planaires , les graphes carrés sont des graphes médians , ce qui signifie que pour tout ensemble de trois sommets u , v et w, il existe un unique sommet médian m ( u , v , w ) appartenant aux plus courts chemins entre chaque paire de ces trois sommets. Comme les graphes médians en général, les graphes carrés sont également des cubes partiels : leurs sommets peuvent être étiquetés par des chaînes binaires de sorte que la distance de Hamming entre les chaînes soit égale à la distance du plus court chemin entre les sommets.

Le graphe obtenu à partir d'un graphe carré en faisant un sommet pour chaque zone (une classe d'équivalence d'arêtes parallèles de quadrilatères) et une arête pour chaque paire de zones qui se rencontrent dans un quadrilatère est un graphe circulaire déterminé par un diagramme de cordes sans triangle du disque unité.

Les squaregraphs peuvent être caractérisés de plusieurs manières autres que par leurs plongements planaires :

• Ce sont les graphes médians qui ne contiennent, comme sous-graphe induit, aucun membre d'une famille infinie de graphes interdits . Ces graphes interdits sont le cube (le graphe simplex de K_₃ ), le produit cartésien d'une arête et d'une griffe K_{_1,3} (le graphe simplex d'une griffe), et les graphes obtenus à partir d'un graphe d'engrenage en ajoutant un sommet supplémentaire relié au moyeu de la roue (le graphe simplex de l'union disjointe d'un cycle avec un sommet isolé).
• Ce sont les graphes qui sont connexes et bipartis , tels que (si un sommet arbitraire r est choisi comme racine ) chaque sommet a au plus deux voisins plus proches de r , et tels qu'à chaque sommet v , le lien de v (un graphe avec un sommet pour chaque arête incidente à v et une arête pour chaque 4-cycle contenant v ) est soit un cycle de longueur supérieure à trois, soit une union disjointe de chemins.
• Ce sont les graphes duaux des arrangements de droites dans le plan hyperbolique qui ne comportent pas trois droites se croisant mutuellement.

La caractérisation des graphes carrés en termes de distance à une racine et de liens des sommets peut être utilisée avec une recherche en largeur dans le cadre d'un algorithme linéaire pour tester si un graphe donné est un graphe carré, sans qu'il soit nécessaire d'utiliser les algorithmes linéaires plus complexes pour tester la planarité de graphes arbitraires.

Plusieurs problèmes algorithmiques sur les graphes carrés peuvent être calculés plus efficacement que dans des graphes planaires ou médians plus généraux ; par exemple, & Vaxès (2002) et & Vaxès (2004) présentent des algorithmes en temps linéaire pour calculer le diamètre des graphes carrés et pour trouver un sommet minimisant la distance maximale à tous les autres sommets.