Arbre SPQR

vignette|360x360px| Un graphe et son arbre SPQR. Les lignes noires pointillés sont des arêtes virtuelles, représentées en noir; les arêtes restantes sont colorées d'après la composant triconnexe à laquelle elles appartiennent. En théorie des graphes, un arbre SPQR est une structure de données arborescente utilisée en informatique, et plus spécifiquement en algorithmique de graphes, pour représenter les composantes triconnexes d'un graphe. L'arbre SPQR d'un graphe peut être construit en temps linéaire ; plusieurs applications dans les algorithmes de graphes dynamiques et dans le tracé de graphes utilisent cette structure de données. Les structures de base sous-jacentes à unarbre SPQR, sont les composantes triconnexes d'un graphe et la relation entre cette décomposition et les plongements planaires d'un graphe planaire; ces relations ont d'abord été étudiés par Saunders Mac Lane ; ces structures ont été utilisées dans des algorithmes efficaces par plusieurs autres chercheurs avant leur formalisation en termes d'arbre SPQR par Di Battista et Tamassia. Un arbre SPQR se présente sous la forme d'un arbre non enraciné dans lequel à chaque nœud x est associé un graphe ou multigraphe non orienté G x, une composante du graphe donné. Les nœuds sont reliés par des arêtes « virtuelles » qui relient les graphes associés, eux aussi dotés d'arêtes virtuelles. Un nœud, et le graphe qui lui est associé, peut être de l'un des quatre types suivants, correspondant aux initiales SPQR: Dans un nœud de type S, le graphe associé est un graphe cycle avec au moins trois sommets et arêtes. Ce cas est analogue à la composition en série dans les graphes série-parallèle ; la lettre « S » signifie « série ». Dans un nœud de type P, le graphe associé est un graphe dipolaire, un multigraphe avec deux sommets et au moins trois arêtes ; c'est le dual planaire d'un graphe cyclique. Ce cas est analogue à la composition parallèle dans graphes série-parallèle ; la lettre « P » signifie « parallèle. Dans un nœud de type Q, le graphe associé a une seule arête réelle.