Graphique en blocs

Ces graphes possèdent également une caractérisation de graphes interdits , car ils n'ont ni le graphe diamant ni un cycle d'au moins quatre sommets comme sous-graphe induit ; autrement dit, ce sont les graphes cordaux sans diamant. Ce sont aussi les graphes ptolémaïques ( graphes cordaux héréditaires par distance ) dans lesquels deux nœuds quelconques, distants de deux, sont reliés par un unique plus court chemin , et les graphes cordaux dans lesquels deux cliques maximales quelconques ont au plus un sommet en commun.

Un graphe est vide ou connexe. Par conséquent, les sous-ensembles connexes de sommets d'un graphe bloc connexe forment une géométrie convexe , une propriété qui n'est pas vraie pour les graphes qui ne sont pas des graphes blocs. Grâce à cette propriété, dans un graphe bloc connexe, tout ensemble de sommets possède un unique sur-ensemble connexe minimal, qui est son adhérence dans la géométrie convexe. Les graphes blocs connexes sont précisément les graphes dans lesquels il existe un unique chemin induit reliant toute paire de sommets.

Les graphes de blocs sont cordaux , héréditaires par distance et géodésiques . Les graphes héréditaires par distance sont ceux dans lesquels deux chemins induits quelconques entre deux mêmes sommets ont la même longueur, ce qui affaiblit la caractérisation des graphes de blocs selon laquelle il existe au plus un chemin induit entre chaque paire de sommets. Puisque les graphes cordaux et les graphes héréditaires par distance sont des sous-classes des graphes parfaits , les graphes de blocs sont parfaits.

Tout arbre , graphe de cluster ou graphe en moulin à vent est un graphe de blocs.

Chaque graphe de blocs a une boxicité d'au plus deux.

Les graphes de blocs sont des exemples de graphes pseudo-médians : pour chaque paire de sommets, soit il existe un unique sommet qui appartient aux plus courts chemins entre les trois sommets, soit il existe un unique triangle dont les arêtes se trouvent sur ces trois plus courts chemins.

Les graphes arêtes d'arbres sont précisément les graphes blocs dans lesquels chaque sommet de coupe est incident à au plus deux blocs, ou, de manière équivalente, les graphes blocs sans griffes . Les graphes arêtes d'arbres ont été utilisés pour trouver des graphes ayant un nombre donné d'arêtes et de sommets dans lesquels le plus grand sous-graphe induit qui est un arbre est le plus petit possible.

Les graphes blocs, où chaque bloc a une taille inférieure ou égale à trois, sont un type particulier de graphe cactus : le cactus triangulaire. Le plus grand cactus triangulaire de tout graphe peut être trouvé en temps polynomial grâce à un algorithme pour le problème de parité des matroïdes . Puisque les graphes cactus triangulaires sont planaires , le plus grand cactus triangulaire peut servir d'approximation du plus grand sous-graphe planaire, un sous-problème important de la planarisation . En tant qu'algorithme d'approximation , cette méthode a un facteur d'approximation de 4/9, le meilleur connu pour le problème du sous-graphe planaire maximal.

Si G est un graphe non orienté quelconque, son graphe par blocs , noté B ( G ), est l' intersection de ses blocs : B ( G ) possède un sommet pour chaque composante biconnexe de G , et deux sommets de B ( G ) sont adjacents si les blocs correspondants se rejoignent en un sommet d'articulation. Si _K₁ désigne le graphe à un seul sommet, alors B ( K₁ ₎ est le graphe vide . B ( G ) est nécessairement un graphe par blocs : il possède une composante biconnexe pour chaque sommet d'articulation de , et chaque composante biconnexe ainsi formée est une clique. Réciproquement, tout graphe par blocs est le graphe B ( G ) d'un certain graphe G. ] Si G est un arbre, alors B ( G ) coïncide avec son graphe d' arêtes .

Le graphe B ( B ( G )) a un sommet pour chaque sommet d'articulation de G ; deux sommets sont adjacents dans B ( B ( G )) s'ils appartiennent au même bloc dans G .