Outils Theoriques pour le Calcul Pratique de

l’Hyperbolicite dans les Grands Graphes

Guillaume Ducoffe

Rapport de Stage M2 MPRISupervise par David Coudert

Equipe COATI, Laboratoire I3S/Inria Sophia Antipolis - Mediterranee

Du 18 Mars 2013 Au 31 Aout 2013

Le contexte general

Ce stage porte sur la notion d’hyperbolicite dans les graphes. L’hyper-bolicite, introduite par Mikhaıl Gromov, mesure la proximite de la metriquedu graphe a celle d’un arbre. De nombreux travaux ont pour objet de ca-racteriser les graphes de faible hyperbolicite, ainsi que d’etudier ses relationsavec d’autres parametres de la theorie des graphes. Son etude est motiveepar la problematique du calcul des routes dans les grands graphes, commeles graphes des systemes autonomes de l’Internet.

Le routage consiste a selectionner les chemins par lesquels transite l’in-formation dans le reseau. Un bon routage doit etre calculable efficacement,et choisir des chemins aussi courts que possible. Une des approches envi-sagees consiste a : plonger le graphe modelisant le reseau dans une structuregeometrique puis, exploiter les coordonnees du plongement pour decider deschemins a emprunter. En general, les plongements dans des espaces Eucli-diens entraınent des distortions importantes des distances entre les sommets.Mais il a ete montre empiriquement que les plongements dans des espaceshyperboliques conduisaient a de meilleurs resultats. L’hyperbolicite mesurela pire distortion (additive) des distances dans un graphe, quand on le plongedans un espace hyperbolique.

Le probleme etudie

L’hyperbolicite d’un graphe peut se calculer en temps O(n4), ou n estle nombre de sommets du graphe. Les temps de calcul sont donc bien trop

1

importants pour des graphes de plus de 10 000 sommets. De plus, au vude resultats obtenus pendant ce stage, il semble peu probable qu’on puissediminuer significativement ce cout.

L’objet de ce stage etait de trouver des proprietes structurelles qui aidenta reduire la complexite, au moins en pratique. Cette approche reste encoreen grande partie a explorer. Les outils classiques en theorie des graphesprennent mal en compte l’aspect metrique du graphe, ce qui rend le problemedifficile et les resultats peu nombreux en la matiere.

La contribution proposee

Dans un premier temps, j’ai montre comment rendre compatible le calcul(exact et approche) de l’hyperbolicite du graphe avec sa decomposition selonses cliques-separatrices. Puis, j’ai repense la caracterisation des graphes defaible hyperbolicite, ce dont j’ai pu deduire un algorithme de reconnaissanceplus efficace que dans le cas general. Ces resultats ont abouti a un algorithmeen temps lineaire pour le calcul de l’hyperbolicite dans les graphes planairesexterieurs. Finalement, j’ai completement determine l’hyperbolicite d’unenouvelle famille de graphes, et j’ai etabli des relations entre hyperbolicite etlargeur arborescente (treewidth), avec des applications algorithmiques dansles deux cas.

Les arguments en faveur de sa validite

La methode de decomposition par des cliques separatrices a ete valideeexperimentalement sur des cartes de l’Internet (CAIDA) ; elle a diminuel’ordre de grandeur des graphes etudies. Par ailleurs mes algorithmes, res-pectivement pour determiner les graphes de faible hyperbolicite et pourles graphes planaires exterieurs, sont theoriquement optimaux pour leursproblemes respectifs. D’autres de mes resultats offrent une premiere etudetheorique d’une recente heuristique, dont la validite n’est pour l’instantqu’experimentale.

Le bilan et les perspectives

Je compte poursuivre mon etude theorique des recentes methodes heuris-tiques pour l’hyperbolicite. En outre, ma methode de decomposition gagne-rait a etre confrontee experimentalement a d’autres types de graphes reels.A ce jour, peu de methodes d’approximation sont connues pour le probleme,et cette piste aussi gagnerait a etre poursuivie. Mais je suis plus interesse parune caracterisation des graphes de faible hyperbolicite (pour de plus largesvaleurs), dont je pense qu’on pourra deduire des algorithmes plus efficaces.

2

Table des matieres

1 Introduction 4

2 Definitions et Etat de l’Art 6

3 Une Methode de Decomposition 93.1 Separer le graphe par une clique . . . . . . . . . . . . . . . . 93.2 Approximation 1-additive pour l’Hyperbolicite . . . . . . . . 113.3 Substitution pour le Calcul Exact . . . . . . . . . . . . . . . . 123.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Graphes de Faible Hyperbolicite 134.1 L’Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.2 Complexite et Discussion . . . . . . . . . . . . . . . . . . . . 15

5 Applications aux Graphes Planaires Exterieurs 165.1 L’Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.2 Discussion et Approximation pour les Graphes Planaires . . . 19

6 Conclusion 20

A Complements a la Section 3 25A.1 Preuves pour la Section 3.1 . . . . . . . . . . . . . . . . . . . 25A.2 Preuves pour la Section 3.2 . . . . . . . . . . . . . . . . . . . 28A.3 Preuves pour la Section 3.3 . . . . . . . . . . . . . . . . . . . 35A.4 Complements pour la Discussion . . . . . . . . . . . . . . . . 37

B Complements a la Section 4 38B.1 Puissances de Graphe et Hyperbolicite . . . . . . . . . . . . . 38B.2 Convexite dans les Graphes . . . . . . . . . . . . . . . . . . . 40B.3 Preuves pour la Section 4.1 . . . . . . . . . . . . . . . . . . . 43

C Complements a la Section 5 46C.1 Graphes Planaires Exterieurs 1/2-hyperboliques . . . . . . . . 46C.2 Graphes Soleil . . . . . . . . . . . . . . . . . . . . . . . . . . . 48C.3 Preuves pour la Section 5.1 . . . . . . . . . . . . . . . . . . . 53

D Hyperbolicite et Largeur Arborescente 56

E Grilles Hexagonales et Contractions d’Aretes 60

3

1 Introduction

L’hyperbolicite a ete introduite par Mikhaıl Gromov pour les groupes detype fini [38]. Elle s’est revelee y jouer un role important, en particulier pourl’etude des groupes automatiques, dont les proprietes servent en theorie deslangages formels [56]. Le concept a ensuite ete etendu aux mathematiquesdiscretes. Ces dernieres decennies ont vu apparaıtre quantite de travaux surce parametre, dans le cadre d’espaces metriques plus generaux. Cette notion,qui ne repose que sur des conditions locales, s’adapte bien aux espaces decourbure negative, dont elle capte les proprietes essentielles.

Les graphes sont des objets combinatoires, utilises par exemple pour lamodelisation des reseaux [25, 26], et qui peuvent etre equipes d’une distance”naturelle” : celle des plus courts chemins. A ce titre, ils s’inscrivent dansl’etude plus generale de l’hyperbolicite dans les espaces metriques, pourlaquelle ils jouent le role d’espace standard : en effet, l’hyperbolicite d’unnombre important d’espaces metriques peut se ramener a celle d’un graphe(eventuellement infini) [58, 60, 61, 70].

Considere pour les seuls graphes des reseaux, le parametre d’hyperboli-cite a amene a de multiples applications pratiques : en routage [12], pourles systemes de securite [42], la diffusion des virus [43], ainsi qu’en bioin-formatique [28]. En particulier pour le graphe de l’Internet, on a observequ’il pouvait etre plonge dans un espace hyperbolique, avec une faible dis-tortion des distances [12] (des mesures experimentales de son hyperbolicitel’ont confirme [21, 24, 45, 55]), ce dont on a pu deduire un algorithme glou-ton pour le probleme du routage [57]. Finalement dans [45, 55], les auteursproposent l’hyperbolicite comme un parametre intrinseque des complex net-works, par le biais duquel on pourrait les classifier, et qui expliquerait cer-taines proprietes de type small world observees pour ces reseaux.

Du point de vue algorithmique, l’hyperbolicite mesure aussi la proximitede la metrique du graphe avec celle d’un arbre, ou graphe connexe acyclique.Les arbres sont des graphes reputes ”faciles”, au sens ou des problemes NP-complets peuvent etre resolus pour eux en temps (quasi-)lineaire, tels quel’ensemble independant de cardinalite maximum, la coloration propre, lalargeur de chemin ou pathwidth [63], la couverture minimale des sommets,etc... Cette simplicite s’etend a des problemes polynomiaux, dont on connaıtdes optimisations pour les arbres, par exemple le calcul du diametre. Pourcette raison, la theorie des graphes comprend de nombreux parametres dontle but est de mesurer la proximite du graphe avec un arbre [11, 27, 71]. Maispeu d’entre eux peuvent etre calcules, ou meme approches, en temps poly-nomial, ce qui rend l’hyperbolicite d’autant plus interessante. Une faible hy-

4

perbolicite conduit effectivement a des optimisations d’algorithmes, notam-ment pour les distance-labeling schemes [35], l’approximation du diametre dugraphe [19], la couverture du graphe par un nombre minimum de boules [20],et le routage compact [47].

En revanche, meme s’il est polynomial, le cout du calcul de l’hyperbolicite(quasiment en temps O(n4), ou n est l’ordre du graphe [33]) n’en reste pasmoins prohibitif pour les grands graphes, de l’ordre de plusieurs milliersde sommets. Certaines des bornes inferieures pour la complexite theorique,obtenues par des reductions, suggerent qu’il ne peut pas en etre autrement(voir la Section 4.2). Des heuristiques ont ete proposees pour reduire le tempsde calcul [21, 24, 45].

L’approche proposee pour ce stage a consiste a determiner quelles pro-prietes structurelles des graphes pouvaient amener a une diminution dutemps de calcul, theorique dans l’ideal, mais au moins pratique. Par exempleune strategie ”diviser pour regner” peut-elle aider ? La difficulte qui se pose,dans ce cas-la, est de pouvoir se ramener a des sous-graphes dont la metriqueest proche de celle du graphe original. Un premier indice qui suggere que cen’est pas chose aisee est que la simple deletion d’une arete du graphe peutmultiplier jusque par cinq la valeur de l’hyperbolicite [15].

Contributions. Sur une suggestion de mon encadrant David Coudert,j’ai d’abord prouve que le calcul de l’hyperbolicite du graphe pouvait etrereduit a celui de l’hyperbolicite de ses sous-graphes obtenus selon la celebredecomposition par les cliques-separatrices minimales de Tarjan [68]. La di-minution de la taille des graphes a considerer peut toutefois s’accompagnerd’une erreur additive de 1 sur la veritable valeur de l’hyperbolicite (Sec-tion 3). Mais cette faible erreur peut cependant etre evitee, au prix d’unemodification des sous-graphes obtenus par la decomposition (Section 3.3).

L’inconvenient majeur de la methode precedente est qu’elle s’adapte malaux graphes de tres petite hyperbolicite (≤ 1

2). J’ai donc etudie ces derniersseparement, en me basant sur la caracterisation bien connue de [3]. J’en aideduit un algorithme de reconnaissance theoriquement optimal des graphes1/2-hyperboliques (Section 4).

Enfin, mon dernier angle d’attaque a ete d’optimiser le probleme pourune classe de graphes en particulier, de sorte que je beneficie d’une structureplus contrainte. J’ai pu ainsi combiner les resultats des Sections 3 et 4 pouraboutir a un algorithme du calcul de l’hyperbolicite en temps lineaire pourles graphes planaires exterieurs (Section 5). Mon travail est complete, en an-

5

nexe, par une etude des relations entre hyperbolicite et largeur arborescente(avec des applications algorithmiques, Section D), et l’analyse preliminaired’une recente heuristique, proposee pour la premiere fois dans [45] (Sec-tion E).

2 Definitions et Etat de l’Art

Un graphe G est une paire formee de deux ensembles (V,E) ; les nelements de V sont appeles les sommets du graphe, et les m elements deE, ou aretes, sont des sous-ensembles de deux sommets distincts. Un som-met contenu dans une arete est une extremite de cette arete, et deux som-mets sont dits adjacents s’ils sont les deux extremites d’une meme arete.On definit aussi, pour tout sommet u ∈ V , son voisinage N(u) comme l’en-semble des sommets du graphe avec lesquels il est adjacent. La terminologieet les resultats standards sur les graphes peuvent etre consultes plus avantdans [13, 26]. Au cours de ce stage, je me suis surtout interesse aux dis-tances dans le graphe (toujours suppose connexe dans la suite, et tel quela longueur de ses aretes est 1). Pour rappel, une distance sur un ensembleX est une fonction d : X ×X → R+, qui satisfait aux trois proprietes quisuivent :

– la symetrie : d(x, y) = d(y, x) ;– la separation : d(x, y) = 0 si, et seulement si, x = y ;– l’inegalite triangulaire : d(x, y) ≤ d(x, z) + d(z, y).

Un ensemble X peut toujours etre equipe d’une distance triviale, definiecomme d(x, x) = 0 et d(x, y) = 1 si x 6= y. Dans le cas des graphes, unedistance canonique plus interessante est celle des plus courts chemins entreles sommets. On la notera dG, ou simplement d s’il n’y a pas d’ambiguıtedans le contexte.

L’hyperbolicite du graphe G a ete definie comme suit par Gromov [38] :

Definition 1 ([38]). Le graphe G est δ-hyperbolique si, pour tout quadrupleta, b, c, d de V , les deux plus grandes des trois sommes parmi S1 = d(a, b) +d(c, d), S2 = d(a, c) + d(b, d), et S3 = d(a, d) + d(b, c) different au plusde 2δ. L’hyperbolicite du graphe, ou δ(G), est le plus petit δ tel que G estδ-hyperbolique.

Cette Definition 1 s’appelle condition des 4 points dans la litterature. Onnotera que, par definition, la valeur de δ(G) est forcement un demi-entier.L’hyperbolicite peut neanmoins s’exprimer par le biais d’autres definitions.Sont donnees ci-apres les deux principales qu’on trouve dans la litterature :

6

Fig. 1: Un triangle δ-fin : chaque cote est dans le δ-voisinage des deux autres.

Definition 2. [Produit de Gromov, [38]] Etant donne un triplet quelconquex, y, r de V , on definit le produit (x|y)r comme etant la difference 1

2(d(x, r)+d(r, y) − d(x, y)). Le graphe G est δ-hyperbolique si, pour tout quadrupletx, y, z, r de V , on a que (x|z)r ≥ min(x|y)r, (y|z)r − δ.

Definition 3. [Condition de Rips, [48]] Etant donne un triplet quelconquex, y, z de V , on appelle triangle geodesique d’extremites x, y, z l’union detrois plus courts chemins dans G, d’extremites respectives x et y, y et z, zet x (voir Figure 1).Le triangle est dit δ-fin si, pour n’importe lequel de ses trois cotes, tous sessommets sont a distance au plus δ des deux autres cotes. Le graphe G estδ-hyperbolique si tous ses triangles geodesiques sont δ-fins.

Les Definitions 1 et 2 sont equivalentes ; ce resultat est exploite dans [33],ou les auteurs ont montre que le produit de Gromov peut se reduire au pro-duit matriciel defini dans [29], ce dont ils ont deduit la meilleure complexitetemporelle connue pour le calcul de l’hyperbolicite. Celle-ci s’exprime enfonction de α, soit le plus petit exposant µ tel qu’on puisse multiplier deuxmatrices carrees a n lignes (et colonnes) en temps O(nµ). Le resultat prin-cipal de [33] est que δ(G) se calcule en temps O(n

5+α2 ). A ce jour, on sait

que α < 2.3727 [22]. D’ou une complexite temporelle O(n3,69).En revanche, les valeurs δ∗(G) et δ(G), donnees respectivement par la

Definition 3 et par la Definition 1 (ou 2) peuvent ne pas etre les memes. Ce-pendant, elles sont intrinsequement reliees. Ainsi, δ∗(G) ≤ 4δ(G) [38], tan-dis que δ(G) ≤ 2δ∗(G) + 1

2 [37]. En particulier, les graphes 0-hyperboliquescorrespondent pour toutes les definitions. D’apres la Definition 3, les arbressont 0-hyperboliques ; en effet, dans un triangle geodesique, tous les sommetsappartiennent a, au moins, deux cotes distincts. La Definition 3 est parfoispreferee par certains auteurs, en raison de ses interpretations geometriques [9].Mais la Definition 1 est la plus adaptee du point de vue algorithmique. Dansla suite, nous retenons donc seulement la condition des 4 points. Etant donne

7

un quadruplet quelconque a, b, c, d de V , nous ecrivons δ(a, b, c, d) la demi-difference entre les deux plus grandes sommes parmi S1, S2 et S3, ce quinous donne δ(G) = maxa,b,c,d∈V δ(a, b, c, d).

Nous terminons cette section par des resultats devenus classiques sur l’hy-perbolicite du graphe.

Le premier s’appuie sur le concept de paires localement eloignees [31].Elles consistent en deux sommets u, v dont on ne peut pas augmenter lo-calement le plus court chemin. En d’autres termes, pour tout u′ ∈ N(u)et pour tout v′ ∈ N(v) on a d(u, v) ≥ maxd(u′, v), d(u, v′). Les sommetsdiametralement opposes dans le graphe sont autant d’exemples de paireslocalement eloignees.

Lemme 4 ( [31]). Soit G = (V,E) un graphe connexe. Il existe deux pairesu1, v1 et u2, v2, toutes les deux localement eloignees, et qui satisfont :

– d(u1, v1) + d(u2, v2) ≥ d(u1, v2) + d(u2, v1) ≥ d(u1, u2) + d(v1, v2) ;– δ(G) = δ(u1, u2, v1, v2).

En clair, le Lemme 4 diminue le nombre de quadruplets a considerer pourla valeur δ(G). Des experimentations ont montre qu’en pratique, l’elagagediminue significativement le temps de calcul [31]. Dans le cas des grilles, iln’y a que deux paires localement eloignees, qui sont respectivement les coinsde la grille diametralement opposes.

Des bornes superieures pour δ(G) ont ete obtenues en fonction d’autresparametres du graphe [53]. Cette etude est brievement completee dans laSection D. Nous resumons dans le Lemme 5 les bornes superieures les pluspertinentes pour notre etude :

Lemme 5. ( [21, 37, 46]) Soit G = (V,E) un graphe connexe, et a, b, c, dun quadruplet de V . On suppose sans perte de generalite d(a, b) + d(c, d) ≥d(a, c) + d(b, d) ≥ d(a, d) + d(b, c). Alors :

– δ(a, b, c, d) ≤ mind(a, b)/2,d(c, d)/2 ;– δ(a, b, c, d) ≤ mind(a, b),d(c, d), d(a, c),d(b, d), d(a, d), d(b, c) ;– δ(a, b, c, d) ≤ bdiam(G)

2 c.

Quant aux bornes inferieures, elles s’obtiennent grace a des sous-graphesisometriques. Le sous-graphe G[X], induit dans G par le sous-ensemble desommets X, est dit isometrique quand il preserve les distances dans G. End’autres termes, pour tout couple x, y de X, on a dG(x, y) = dG[X](x, y).Clairement, δ(G[X]) ≤ δ(G) des que cette condition est verifiee. C’est lecas, en particulier, quand le sous-ensemble X est une composante biconnexe

8

de G. En fait, un resultat plus fort dit que l’hyperbolicite de G est egalea l’hyperbolicite maximum prise sur tous les sous-graphes induits par sescomposantes biconnexes. Aussi, dans la suite, on supposera souvent, sansperte de generalite, que le graphe G considere est au moins 2-connexe.

Afin d’etre exploitee dans un contexte plus general, cette methode re-quiert neanmoins de connaıtre des familles de graphes simples dont l’hyper-bolicite a ete completement caracterisee. Nous presentons ici deux d’entreelles : les cycles et les grilles.

Lemme 6. ( [21, 72]) Les cycles d’ordre 4p+ ε, ou p ≥ 1 et ε ∈ 0, 1, 2, 3,sont (p− 1/2)-hyperboliques si ε = 1, et p-hyperboliques sinon.

Lemme 7. ( [21]) Les grilles n×m sont (minn,m − 1)-hyperboliques.

3 Une Methode de Decomposition

Rappelons qu’un ensemble X ⊂ V est un separateur dans le grapheconnexe G si G[V \ X] n’est plus connexe. Si de plus G[X] est un sous-graphe complet, on dit que X est une clique-separatrice pour G. Dans cettesection, nous supposerons, pour simplifier, notre graphe d’etude G biconnexeet δ(G) ≥ 1. Le cas des graphes 1/2-hyperboliques sera traite a part dansla Section suivante. Nous prouverons qu’on peut reduire la taille de G enrecourant a une decomposition selon les cliques-separatrices minimales [68].Cette decomposition (unique [50]) est la donnee de tous les sous-graphesmaximaux qui n’admettent pas de cliques-separatrices (nous les appelle-rons atomes). Elle est calculable en temps O(nm) [50, 68]. Notre but estde montrer qu’on obtient δ(G) (a une constante additive pres) rien qu’encalculant l’hyperbolicite de chacun des atomes. Un resultat qui s’ajoute auxquelques decompositions deja connues pour preserver l’hyperbolicite, dontla decomposition modulaire et la split decomposition [37]. Nous sommes ca-pables de calculer la valeur exacte si necessaire, grace a une modificationdes atomes (Section 3.3).

Quelques notations s’imposent pour la suite. On appelle (A|B)-separateurtout sous-ensemble X qui deconnecte les sommets a ∈ A\X des sommetsb ∈ B\X. En particulier, A et B sont deux (A|B)-separateurs triviaux. Onreserve la notation (a|b1, b2, b3) aux quadruplets tels que a ∈ A et b1, b2, b3 ∈B, la notation (a1, a2|b1, b2) a ceux tels que a1, a2 ∈ A et b1, b2 ∈ B. Lespreuves manquantes peuvent etre consultees en Section A.

3.1 Separer le graphe par une clique

Notre algorithme est le suivant. Soit X un separateur du graphe ;

9

– Considerer separement chaque composante connexe B de G[V \X] ;– Calculer l’hyperbolicite de chaque sous-graphe G[B ∪X] ;– Retourner la plus grande des valeurs ainsi calculees.

J’ai d’abord demontre que si X est une clique-separatrice, alors la methodeci-dessus retourne toujours l’hyperbolicite du graphe G (a une faible distor-sion additive pres). Ce resultat avait ete demontre independamment dans [37].Toutefois, mes techniques sont generalisables a la decomposition du graphepar plusieurs cliques-separatrices (voir la Section suivante), et elles donnentdavantage d’information sur la structure des quadruplets a prendre en comptepour δ(G) que n’en donne la preuve plus calculatoire de [37].

Theoreme 8. ( [37]) Soit G un graphe biconnexe tel que δ(G) ≥ 1. Etantdonne une clique-separatrice X pour G, soient B1, . . . , Bk les composantesconnexes de G[V \X]. On a que : max1≤i≤k δ(G[Bi∪X]) ≤ δ(G) ≤ max1≤i≤k δ(G[Bi∪X]) + 1/2.

La borne inferieure vient de ce que, puisque un sous-graphe complet estisometrique, alors tous les sous-graphes G[Bi ∪X] consideres le sont aussi.D’un autre cote, il peut advenir que la valeur δ(G) n’est atteinte qu’endes quadruplets a, b, c, d qui ont ete separes par X. Nous montrerons qu’untel quadruplet extremal doit satisfaire des conditions sur la distance de sessommets a X, ce dont on deduira la borne superieure du Theoreme 8.

D’abord montrons que les quadruplets du type (a1, a2|b1, b2) ont unehyperbolicite bornee par DX , ou DX est le diametre de X dans G (i.e., laplus longue distance dans G entre les sommets dans X).

Lemme 9. ( [21]) Soit X un (A|B)-separateur de diametre DX dans ungraphe connexe G. Alors pour tout quadruplet de type (a1, a2|b1, b2) on a queδ(a1, a2, b1, b2) ≤ DX .

Demonstration. Rappelons que S1 = d(a1, a2) + d(b1, b2), S2 = d(a1, b1) +d(a2, b2), et S3 = d(a1, b2) + d(a2, b1). On suppose sans perte de generaliteS2 ≥ S3. Soit d(v,X) la notation pour la plus courte distance entre unsommet v et un sommet de X.

Clairement, d(ai, bi) ≥ d(ai, X) + d(X, bi) pour tout i = 1, 2,et d(ai, aj) ≤ d(ai, X) + d(aj , X) +DX avec i, j = 1, 2.

Si S1 ≥ S2, on obtient :S2 = d(a1, b1) + d(a2, b2)≥ d(a1, X) + d(X, b1) + d(a2, X) + d(X, b2)≥[

d(a1, X) + d(a2, X) +DX

]+[

d(b1, X) + d(b2, X) +DX

]− 2DX

≥ S1 − 2DX .

10

En consequence on a δ(a1, a2, b1, b2) ≤ (S1 − S2)/2 ≤ DX .On montre de meme que S3 ≥ S2 − 2DX , et quand S2 ≥ S1 que S1 ≥

S2 − 2DX . D’ou finalement δ(a1, a2, b1, b2) ≤ DX dans tous les cas.

En particulier lorsque X est une clique-separatrice on a DX = 1, et doncδ(a1, a2, b1, b2) ≤ 1. Cela signifie que nous pouvons ignorer tous ces quadru-plets, sous l’hypothese que δ(G) est au moins 1. Cependant, il e des graphesou δ(G) est seulement atteint par des quadruplets de type (a|b1, b2, b3). Lereste de la preuve du Theoreme 8 (voir Section A) consiste a determinersous quelles conditions (necessaires) un tel cas survient, et d’en deduire laborne superieure en jouant sur la structure de ces quadruplets.

Notons, pour conclure cette Section, que cette borne superieure est lameilleure possible. Pour le voir, soit le graphe G construit depuis un cycle C7

de longueur 7 auquel on ajoute un sommet i′ et les aretes i, i′ et i′, i+ 1pour tout i ∈ Z7. C’est donc un graphe avec 14 sommets. Les trianglesi, i+ 1, i′ sont 0-hyperboliques, et C7 a pour hyperbolicite 1. Neanmoins,l’hyperbolicite de G est 3/2.

3.2 Approximation 1-additive pour l’Hyperbolicite

Nous savons par la Section precedente que la separation du graphe parune clique peut entraıner une (faible) erreur additive sur la vraie valeur del’hyperbolicite. Nous montrons maintenant que le calcul de l’hyperboliciteen fonction des seuls atomes donne une approximation additive a 1 presde la valeur du parametre. C’est-a-dire que l’erreur possible induite par lesseparations ne peut pas s’accumuler.

Theoreme 10. Etant donnee la decomposition par les cliques-separatricesde G = (V,E), soient Bi les atomes du graphe. On a que : maxi δ(G[Bi]) ≤δ(G) ≤ maxi δ(G[Bi]) + 1

On notera qu’en particulier, le Theoreme 10 donne une nouvelle preuveque les graphes cordaux sont 1-hyperboliques. Un graphe G est cordal si, etseulement si, il n’y a pas de cycle induit de taille au moins 4 dans G.

Corollaire 11. ( [14]) Soit G = (V,E) un graphe cordal.Alors on a que : δ(G) ≤ 1.

Demonstration. Pour rappel, un sommet v ∈ V est dit simplicial si G[N(v)]est un sous-graphe complet. Il est bien connu que G est cordal si, et seule-ment si, soit G est trivial (e.g. c’est un unique sommet sans arete), soitil existe un sommet simplicial v ∈ V tel que G \ v est egalement cor-dal [62]. Cette caracterisation implique que tous les atomes de G sont des

11

sous-graphes complets, donc d’hyperbolicite 0. En consequence, δ(G) ≤ 1d’apres le Theoreme 10.

La preuve, assez technique, du Theoreme 10 est detaillee dans la Sec-tion A. Son argument principal est que si a, b, c, d ∈ V appartiennent a desatomes differents, et δ(a, b, c, d) > 1, alors on peut trouver un atome A parlequel passent tous les plus courts chemins entre ces sommets, et tels queδ(a, b, c, d) ≤ δ(G[A])+1.

3.3 Substitution pour le Calcul Exact

Nous avons dit precedemment que lors de la separation du graphe parune clique X, notre algorithme de la Section 3.1 peut retourner une valeurerronee pour l’hyperbolicite de G, mais seulement si δ(G) est uniquement at-teint pour des quadruplets de type (a|b1, b2, b3), separes parX et qui verifientdes conditions necessaires sur leurs distances a X. On propose, dans la Sec-tion A en annexe, une modification des atomes pour prendre en comptecette eventuelle erreur sur l’hyperbolicite. L’idee est d’ajouter des sommetssimpliciaux aux atomes, dont le voisinage est un sous-ensemble d’une clique-separatrice, et qui simulent le sommet a d’un possible quadruplet du type(a|b1, b2, b3). La difficulte technique est de s’assurer que l’addition de nou-veaux sommets n’augmente pas artificiellement la valeur de l’hyperbolicitede G.

Notre construction requiert de connaıtre les cliques-separatrices Xi quiont ete employees pendant la decomposition. La modification des atomesdemande un temps qui leur est directement proportionnel, soit O(nΣi|Xi|).Dans le pire des cas, les substituts obtenus pour les atomes ont une taille del’ordre de G, auquel cas le benefice obtenu par la decomposition est perdu(quoique la structure du graphe puisse avoir ete simplifiee). Mais cette taillene depasse jamais celle du graphe d’etude.

3.4 Discussion

La methode de decomposition par les cliques-separatrices minimales aete employee sur des graphes de l’Internet, pour lesquels on a pu montrerexperimentalement un gain reel en la taille des graphes d’etude, meme apresles substitutions de la Section 3.3 [21].

Plusieurs generalisations possibles a ce travail ont ete considerees pen-dant le stage. Par exemple, une extension naturelle serait de borner l’er-reur sur l’hyperbolicite pour des decompositions par des separateurs deplus grand diametre que 1. Cela semble toutefois peu prometteur, car tousles graphes sont completement separables rien que par des separateurs de

12

diametre (au plus) 2 : les voisinages des sommets du graphe. Meme secontraindre a des separateurs isometriques n’est pas assez ; en effet, lesgraphes pontes (ou bridged graphs) sont completement separables par desseparateurs isometriques de diametre au plus 2, alors qu’on peut trou-ver des graphes dans cette classe avec une hyperbolicite arbitrairementgrande [1, 46].

Nous avons aussi cherche a reduire le calcul de l’hyperbolicite du graphea celui de l’hyperbolicite de ses composantes triconnexes. Celles-ci sont obte-nues en temps lineaire par la decomposition du graphe selon ses separateursde taille 2 [40]. Dans le cas ou les deux sommets d’un meme separateursont adjacents, on a une arete-separatrice. Ce cas particulier est donc prisen compte par notre methode pour la clique-decomposition. Mais il resteencore a trouver comment prendre en compte le cas ou les deux sommets duseparateur ne sont pas adjacents.

De plus amples details sont disponibles en annexe (Section A), ou desgeneralisations dans des cadres plus contraints sont proposees.

4 Graphes de Faible Hyperbolicite

Meme si le temps de calcul pour l’hyperbolicite reste prohibitif, on peutesperer que reconnaıtre un graphe de tres petite hyperbolicite puisse etrerealisable plus efficacement. Formellement, on se donne une constante δ, etnotre but est d’analyser la complexite du probleme de decider si un grapheG = (V,E) est δ-hyperbolique (i.e. δ(G) ≤ δ). Les raisons pratiques nemanquent pas. L’une d’elles est qu’on s’attend a ce que les graphes de faiblehyperbolicite soient les instances les plus difficiles pour l’algorithme proposeedans [21]. Par ailleurs, plusieurs graphes reels, comme ceux de l’Internet,sont deja connus pour avoir une hyperbolicite bornee [12, 24]. Enfin, descaracterisations plus poussees existent pour ces graphes, dont on aspire adegager de nouveaux outils pour nos algorithmes.

Un resultat bien connu dit que les graphes 0-hyperboliques sont exac-tement les cactus de cliques (block graphs) : ceux dont les composantesbiconnexes sont des sous-graphes complets [6, 41]. La reconnaissance deces graphes en temps lineaire s’en deduit simplement. Par contraste, la ca-racterisation des graphes 1/2-hyperboliques [3] n’a, pour ce que nous en sa-vons, jamais abouti a une application algorithmique d’aucune sorte. L’objetprincipal de cette Section sera de presenter un algorithme de reconnaissancedes graphes 1/2-hyperboliques, qui est base sur leur caracterisation. Le detaildes preuves pour cette Section est consultable en annexe en Section B

13

Fig. 2: Les six sous-graphes isometriques interdits.

4.1 L’Algorithme

Dans la suite, un sous-graphe induit H qui n’est pas isometrique est ditponte. Le graphe G est sans H si, et seulement si, H n’est pas un sous-grapheinduit de G. Chepoi et al. on donne dans [3] une caracterisation completedes graphes 1/2-hyperboliques basee sur des sous-graphes isometriques in-terdits :

Theoreme 12 ( [3]). Soit G = (V,E) un graphe connexe. G est 1/2-hyperbolique si, et seulement si, tous les cycles dans G de longueur 4 ouau moins 6 sont pontes, et aucun des graphes de la Figure 2 n’est un sous-graphe isometrique de G.

Au contraire de la caracterisation des graphes 0-hyperboliques, il n’estpas clair qu’un algorithme puisse se deduire facilement du Theoreme 12.Decider si H est un sous-graphe isometrique de G est NP-complet quandH fait partie de l’entree (voir [51]). De plus, meme les rares instances quisont connues pour etre dans P requierent un temps de calcul important, parexemple, le probleme du plus long cycle isometrique [51]. Nous montreronspourtant que, de maniere surprenante, un algorithme plus efficace peut sededuire du Theoreme 12.

Nous supposerons dans la suite que la condition suivante est satisfaite :

Condition 1. Tout cycle dans G de longueur au moins 8 est ponte.

D’apres le Theoreme 12, la Condition 1 est necessaire pour qu’un graphesoit 1/2-hyperbolique. En fait elle est necessaire pour qu’un graphe G soit1-hyperbolique d’apres le Lemme 6. Aussi, un moyen commode de verifierla Condition 1 est d’utiliser d’abord une 2-approximation pour l’hyperboli-cite. Si l’approximation retourne plus que 2, alors le graphe n’est pas 1/2-hyperbolique. Sinon, le graphe est 1-hyperbolique et donc, la Condition 1est satisfaite. Un algorithme de 2-approximation peut etre execute en tempsO(n

3+α2 ) = O(n2,69) [33].

A present, notre but est de prouver que les conditions restantes pourque le graphe d’etude G soit 1/2-hyperbolique peuvent etre ramenees a larecherche de cycles induits de longueur 4 (aussi appeles C4, ou quadrangles),dans un petit nombre de graphes qui sont bases sur les puissances de G. Pourrappel, la jeme puissance de G = (V,E) est le graphe Gj = (V,Ej), avec Ejl’ensemble des couples de sommets distincts dans V qui sont a distance auplus j dans G. En d’autres termes : Ej = u, v : 0 < dG(u, v) ≤ j.

Le premier graphe que nous considererons est le carre G2 de G. Le secondest defini comme suit :

14

G G3

edges of G + pseudo-loops (u,0), (u,1)

2

Fig. 3: La construction du graphe G′.

Definition 13. Soit G = (V,E) un graphe connexe. Le graphe G′ = (V ′, E′)a pour sommets V ′ = V ×0, 1 et pour ensemble d’aretes E′, avec E′ definicomme suit :

– le sous-graphe induit G[V × 0] est isomorphe a G (par l’isomor-phisme qui envoie v sur (v, 0)) ;

– le sous-graphe induit G[V × 1] est isomorphe a G3 (par l’isomor-phisme qui envoie v sur (v, 1)) ;

– pour tout u, v ∈ V tel que 0 ≤ dG(u, v) ≤ 2, les sommets (u, 0) et(v, 1) sont adjacents dans G′.

La troisieme condition doit se comprendre comme l’ajout, entre les som-mets de V × 0 et ceux de V × 1, d’aretes en correspondance avec cellesde G2, plus des aretes (u, 0), (u, 1) pour chaque sommet u de V . Une abs-traction de notre construction est presentee sur la Figure 3. On notera queconstruire G2 et G′ demande seulement la connaissance de la matrice desdistances dans G, d’ou une construction des deux graphes possible en tempsO(nα) [64]. Par ailleurs, il est utile d’observer que le nombre de sommetsdans G2 et G′ est du meme ordre de grandeur Θ(n) que dans G.

Nous sommes finalement en mesure d’enoncer notre resultat majeur dela Section :

Theoreme 14. Soit G = (V,E) un graphe connexe qui satisfait la Condi-tion 1. Alors G est 1/2-hyperbolique si, et seulement si, G′ et G2 sont sansC4 (induit), ou G′ represente le graphe de la Definition 13.

La preuve du Theoreme 14 est redigee en annexe dans la Section B.A noter que les graphes sans C4 peuvent etre reconnus en temps O(nα+1),

ce qui est donc le terme dominant pour la complexite de notre algorithme [66].En comparaison, on ne sait pas calculer l’hyperbolicite moins qu’en tempsO(n

5+α2 ) [33]. En prenant α = 2.3727, la complexite dans le pire des cas

de notre algorithme est ainsi n3−α

2 = n0.31365 fois mieux que celle de l’algo-rithme dans [33].

4.2 Complexite et Discussion

Notre algorithme en Section 4.1 a beau avoir ameliore la meilleure com-plexite en temps connue pour decider si un graphe est 1/2-hyperbolique, le

15

cout du temps de calcul reste tres important en comparaison de l’algorithmeen temps lineaire pour les block graphs. Pareille situation amene a se deman-der si la reconnaissance des graphes d’hyperbolicite 1/2 est intrinsequementplus difficile que celle des graphes 0-hyperboliques. La question reste ou-verte. Mais la Proposition 15 tendrait a prouver que c’est le cas. Notons quecette reduction etait deja connue par la communaute [37, 72]. Toutefois, anotre connaissance, sa preuve, bien que simple, n’a jamais ete formellementredigee dans un article :

Proposition 15. Il existe une reduction en temps lineaire du probleme dereconnaissance des graphes sans C4 a celui des graphes 1/2-hyperboliques.

Demonstration. Soit G = (V,E) un graphe non dirige. Nous construisonsle graphe G′ = (V ′, E′) a partir de G en lui ajoutant un sommet universelu /∈ V . Formellement : V ′ = V ∪ u, et E′ = E ∪ u, v : v ∈ V .On observe que, par construction, le diametre de G′ est au plus 2. Donc,δ(G′) ≤ 1 d’apres le Lemme 5.

D’apres le Theoreme 12, G′ est 1/2-hyperbolique si, et seulement si, tousles cycles de taille 4 ou au moins 6 dans G′ sont pontes, et aucun des graphesde la Figure 2 n’est un sous-graphe isometrique de G′. Or, tous les cyclesde taille au moins 6 ont pour diametre au moins 3, et tous les graphes de laFigure 2 ont un diametre strictement plus grand que 2. Il s’ensuit qu’ils nepeuvent pas etre des sous-graphes isometriques d’un graphe de diametre 2.

Finalement G′ est 1/2-hyperbolique si, et seulement si, G est sans C4.

A noter egalement qu’il a ete prouve dans [31] que le calcul de l’hyperbo-licite est au moins aussi dur que celui du diametre d’un graphe. Cependant,la reduction des auteurs requiert des graphes ponderes, la ou des graphesnon ponderes suffisent pour la notre. En outre, des algorithmes en temps(sous-)cubique existent pour le probleme du diametre, alors qu’aucun n’estconnu a l’heure actuelle pour la reconnaissance des graphes sans quadrangle.

Dans le cas des graphes a largeur d’arborescence bornee, la Section Dpropose une methode pour rendre lineaire notre algorithme.

5 Applications aux Graphes Planaires Exterieurs

L’approche classique pour resoudre des problemes difficiles consiste ase contraindre a des familles de graphes dont la structure peut etre mieuxexploitee. Souvent il s’agit de graphes aux proprietes ”geometriques” ; unchoix qui a du sens quand on considere les graphes des reseaux comme desinstallations materielles. Un graphe est planaire si, et seulement si, il peut

16

etre plonge dans le plan sans qu’aucune arete n’en intersecte une autre,sauf eventuellement en leurs extremites. En particulier, tous les cycles et lesgrilles sont planaires. Donc l’hyperbolicite de cette classe de graphes n’estpas bornee (Lemmes 6 et 7). La representation d’un graphe planaire dans leplan est une carte planaire.

Les graphes planaires exterieurs sont une celebre sous-famille de graphesplanaires, a la base d’algorithmes d’approximation pour les graphes planairesgeneraux [2] : ils consistent en ceux pour lesquels il existe une carte planairedont tous les sommets sont sur un meme cercle C et dont toutes les aretessont contenues dans le disque delimite par C ; nous appellerons ce genrede carte planaire un plongement planaire exterieur. De maniere analogue, ils’agit des graphes dont la planarite est preservee quand on leur ajoute unsommet universel u. D’apres le Theoreme de Kuratowski, cette deuxiemecaracterisation implique qu’un graphe est planaire exterieur si, et seulementsi, il est (K4,K2,3)-minor free [69]. Puisqu’une carte planaire peut etre cal-culee en temps lineaire [67], elle entraıne egalement un algorithme en tempslineaire pour calculer un plongement planaire exterieur.

Nous presenterons dans cette Section un algorithme en temps lineairepour le calcul de l’hyperbolicite dans les graphes planaires exterieurs, basesur les resultats des sections precedentes. La reconnaissance des graphesplanaires exterieurs qui sont 1/2-hyperboliques est traitee a part. Puis dansle reste des cas, nous decomposons le graphe selon ses aretes-separatrices(cas particulier des cliques-separatrices), jusqu’a ce qu’on obtienne les facesde la carte planaire comme atomes. Alors, les resultats sur l’hyperbolicitedes cycles peuvent s’appliquer. Nous utilisons finalement l’arbre dual (weakdual) afin de prendre en compte les quadruplets du type (a|b1, b2, b3) (voirla Section 3 pour rappel de la notation).

Le plus gros des preuves est omis, et elles peuvent etre retrouvees dansla Section C.

5.1 L’Algorithme

Comme annonce, nous montrerons le resultat suivant :

Theoreme 16. Soit G = (V,E) un graphe planaire exterieur connexe. Lavaleur δ(G) est calculable en temps lineaire.

D’abord, on rappelle que decider si G a pour hyperbolicite 0 se fait entemps lineaire. On montre en annexe (Section C) que la caracterisation duTheoreme 12 implique un algorithme en temps lineaire pour reconnaıtreles graphes planaires exterieurs qui sont 1/2-hyperboliques. Aussi, dans la

17

Fig. 4: Un exemple de graphe planaire exterieur avec son arbre dual (enrouge). Les substituts des atomes sont donnes a droite.

suite, on supposera G biconnexe et δ(G) ≥ 1. On observe que les faces d’unplongement planaire exterieur de G sont exactement ses cycles isometriques,et egalement ses atomes (definis en Section 3). Donc la decomposition de Gselon ses cliques-separatrices minimales est calculable en temps lineaire.

Reste a obtenir la valeur exacte pour δ(G) par la methode de substitutiondes atomes, qu’on a defini en Section 3.3. Dans le cas ou l’atome est uncycle, son substitut s’obtient par l’ajout de sommets dont le voisinage estune unique arete du cycle d’origine (voir la Section C.2 pour une definitionplus formelle). Les substituts peuvent etre calcules en temps lineaire gracea l’arbre dual de G, note TG. Ses sommets sont les atomes de G, et deuxatomes sont adjacents dans TG si, et seulement si, ils partagent une arete-separatrice.

Une preuve est donnee en annexe mais, intuitivement, une arete-separatricedans un atome C doit etre completee (dans le substitut) par un sommet dontelle est le voisinage si, et seulement si, il y a un sommet dans G separe deC par cette arete et a egale distance de ses deux extremites. Cela vient dece que si le sommet separe a est plus proche d’une extremite x de l’arete-separatrice que de l’autre, alors les sommets de C ne distinguent pas a dex (e.g. tous les chemins vers a peuvent passer par x). Soit donc une areteseparatrice e = x, y dans C, et soit C ′ l’unique cycle isometrique de G apartager cette arete avec C. Clairement, si C ′ est de longueur impaire, alorsil existe un sommet dans C ′ diametralement oppose a e, et donc l’arete edoit etre completee par un sommet dans le substitut de C. Sinon, C ′ est delongueur paire, et il faut considerer l’arete e′ diametralement opposee a edans C ′. Par une application recursive de l’argument precedent, on trouvedans ce cas que e doit etre completee par un sommet dans le substitut de Csi, et seulement si, e′ est aussi une arete-separatrice, et qu’elle est completeepar un sommet dont elle est le voisinage dans le substitut de C ′.

Ainsi, nous pouvons enraciner TG en un atome arbitraire Cr, puis nousdemarrons un parcours en profondeur depuis Cr et, pour chaque cycle isometriquevisite C nous procedons comme suit :

– pour chaque descendant C ′ de C dans l’arbre, nous visitons d’abord

18

le sous-arbre enracine en C ′ ;– soit e l’unique arete-separatrice commune a C et C ′ ;– si C ′ est de longueur impaire, alors on complete e dans le substitut deC par un sommet dont elle est le voisinage ;

– sinon, soit e′ l’arete diametralement opposee a e dans C ′ ;– on complete e par un sommet dans le substitut de C si, et seulement

si, e′ a ete completee de meme dans le substitut de C ′.L’algorithme ci-dessus est correct, mais il est incomplet puisque, pour chaqueatome de G autre que la racine Cr, il demeure une arete-separatrice pourlaquelle nous n’avons pas encore conclu, a savoir : celle entre l’atome etson parent dans l’arbre (TG, Cr). Cependant, puisque le substitut de Cr estcompletement connu des la premiere etape, ces informations manquantessont aisement obtenues a l’aide d’un parcours en largeur de TG depuis Cr.

Finalement, pour chaque cycle isometrique C de G, on calcule l’hyperbo-licite de son substitut, et on retourne pour δ(G) la valeur maximum calculee.L’idee est d’enumerer les quadruplets du cycle pour lesquels δ(C) est atteint,et de verifier pour chacun d’eux si la valeur δ(C) peut etre localement aug-mentee, en remplacant un ou plusieurs des sommets du quadruplet par dessommets voisins (ajoutes pendant la construction du substitut). On abou-tit a un calcul de l’hyperbolicite du substitut de C en temps O(nc), ou ncdesigne la longueur du cycle (voir Section C) Comme la somme des taillesde chaque atome est d’ordre lineaire dans un graphe planaire exterieur (cesont les faces d’une carte planaire de G), on en deduit un temps lineairepour cette derniere etape de calcul. Les details techniques sont traites plusavant en annexe.

5.2 Discussion et Approximation pour les Graphes Planaires

L’algorithme de la Section 5.1 est un premier pas vers une resolutionefficace du probleme de l’hyperbolicite dans les graphes planaires generaux.Nous esperons pouvoir en deduire une approximation de l’hyperbolicite pources graphes, voire un algorithme exact. Cette methodologie est celle suiviepar de nombreux algorithmes d’approximation pour les graphes planaires [2].Les graphes planaires exterieurs sont a la base, notamment, d’algorithmesefficaces pour la resolution du probleme des plus courts chemins dans ungraphe planaire [34], selon une decomposition qui a ete generalisee ensuiteaux autres graphes [44]. Cette utilisation de la ”decomposition en hamac”(hammock decomposition [34]) pour le calcul de plus courts chemins suggerequ’elle est compatible avec l’aspect metrique du graphe, donc avec le calculde l’hyperbolicite. Enfin, en certains cas, les auteurs ont montre qu’il impor-tait surtout d’obtenir une decomposition en des sous-graphes de faible lar-

19

geur d’arborescence [30], ce qui donne aussi un interet nouveau aux resultatspreliminaires de la Section D. Les pistes ci-dessus sont parmi mes prochainssujets de recherche.

6 Conclusion

Pendant ce stage, j’ai montre qu’un grand nombre de cliques-separatricesdans un graphe aidait a decroıtre le temps de calcul de son hyperboli-cite. Ce resultat structurel est une nouvelle application de la decompositioninventee par Tarjan dans [68]. Sur le plan theorique, la methode donneune preuve differente de l’hyperbolicite bornee de nombreuses classes degraphes [14, 36, 52], qui n’utilise pas la cordalite comme en [72]. En pra-tique, elle a permis de serieusement reduire la taille des graphes de l’In-ternet consideres dans [21]. La decomposition gagnerait a present a etreexperimente sur d’autres complex networks, par exemple les cartes routieresetudiees dans [45].

Par ailleurs, j’ai montre l’equivalence, a une reduction pres (en tempssous-cubique), entre les problemes de reconnaissance des graphes 1/2-hyperboliqueset des graphes sans cycle induit de taille 4. Cette nouvelle caracterisationdes graphes 1/2-hyperboliques offre pour resultat surprenant que les sixsous-graphes isometriques interdits qui ont ete mis en evidence dans [3, 46]ne sont en fait que des quadrangles deguises dans une version modifiee dugraphe de depart, ou les perturbations engendrees par les distances ont eteprises en compte. L’algorithme de reconnaissance obtenu par la reduction,de complexite temporelle O(n1+α) = O(n3,3727), est theoriquement plus ef-ficace que l’algorithme de [33] pour le calcul de l’hyperbolicite dans le casgeneral.

Finalement, j’ai pu combiner les deux resultats principaux des Sectionsprecedentes pour aboutir a un algorithme en temps lineaire pour le cal-cul de l’hyperbolicite dans les graphes planaires exterieurs. Transformer cetalgorithme en une methode efficace (exacte ou approchee) du calcul de l’hy-perbolicite dans les graphes planaires generaux est un des objectifs majeursde la poursuite de mes recherches dans ce domaine.

Les travaux de mon stage vont faire l’objet de publications.

References

[1] Richard P Anstee and Martin Farber. On bridged graphs and cop-wingraphs. Journal of Combinatorial Theory, Series B, 44(1) :22–28, 1988.

20

[2] Brenda S Baker. Approximation algorithms for np-complete problemson planar graphs. Journal of the ACM (JACM), 41(1) :153–180, 1994.

[3] Hans-Jurgen Bandelt and Victor Chepoi. 1-hyperbolic graphs. SIAMJournal on Discrete Mathematics, 16(2) :323–334, 2003.

[4] Hans-Jurgen Bandelt and Victor Chepoi. Metric graph theory andgeometry : a survey. Contemporary Mathematics, 453 :49–86, 2008.

[5] Hans-Jurgen Bandelt, Anja Henkmann, and Falk Nicolai. Powers ofdistance-hereditary graphs. Discrete Mathematics, 145(1) :37–60, 1995.

[6] Hans-Jurgen Bandelt and Henry Martyn Mulder. Distance-hereditarygraphs. Journal of Combinatorial Theory, Series B, 41(2) :182–208,1986.

[7] Sergio Bermudo, H. Fernau, Jose M Rodrıguez, and Jose M Sigarreta.Discretization and small values of the hyperbolicity constant in graphs.Submitted.

[8] Sergio Bermudo, Jose M Rodrıguez, Jose M Sigarreta, and W. Carbal-losa. On the hyperbolicity of edge-chordal and path-chordal graphs.Submitted.

[9] Sergio Bermudo, Jose M Rodrıguez, Jose M Sigarreta, and Jean-Marie Vilaire. Gromov hyperbolic graphs. Discrete Mathematics,313(15) :1575–1585, 2013.

[10] Hans L Bodlaender. Planar graphs with bounded treewidth. RUU-CS,(88-14), 1988.

[11] Hans L Bodlaender. Discovering treewidth. In SOFSEM 2005 : Theoryand Practice of Computer Science, pages 1–16. Springer, 2005.

[12] M. Boguna, F. Papadopoulos, and D. Krioukov. Sustaining the Internetwith Hyperbolic Mapping. Nature Communications, 1(62), Oct 2010.

[13] John Adrian Bondy and Uppaluri Siva Ramachandra Murty. Graphtheory with applications, volume 290. Macmillan London, 1976.

[14] G. Brinkmann, J. H. Koolen, and V. Moulton. On the hyperbolicity ofchordal graphs. Annals of Combinatorics, 2001.

[15] Walter Carballosa, Domingo Pestana, Jose M Rodrıguez, and Jose MSigarreta. Distortion of the hyperbolicity constant of a graph. theelectronic journal of combinatorics, 19(1) :P67, 2012.

[16] J. Chalopin, V. Chepoi, P. Papasoglu, and T. Pecatte. Cop and robbergame and hyperbolicity. ArXiv e-prints, August 2013.

21

[17] Jeremie Chalopin, Victor Chepoi, Nicolas Nisse, and Yann Vaxes. Copand robber games when the robber can hide and ride. Siam Journal onDiscrete Mathematics, 25(1) :333–359, 2011.

[18] Shiva Chaudhuri and Christos D Zaroliagis. Shortest path queries in di-graphs of small treewidth. In Automata, Languages and Programming,pages 244–255. Springer, 1995.

[19] V. Chepoi, F. F. Dragan, B. Estellon, M. Habib, and Y. Vaxes. Noteson diameters, centers, and approximating trees of delta-hyperbolic geo-desic spaces and graphs. Electronic Notes in Discrete Mathematics,31 :231–234, 2008.

[20] Victor Chepoi and Bertrand Estellon. Packing and covering δ-hyperbolic spaces by balls. In Approximation, Randomization, andCombinatorial Optimization. Algorithms and Techniques, pages 59–73.Springer, 2007.

[21] N. Cohen, D. Coudert, and A. Lancin. Exact and approximate algo-rithms for computing the hyperbolicity of large-scale graphs. Rapportde recherche RR-8074, INRIA, September 2012.

[22] Don Coppersmith and Shmuel Winograd. Matrix multiplication viaarithmetic progressions. Journal of symbolic computation, 9(3) :251–280, 1990.

[23] Bruno Courcelle. The monadic second-order logic of graphs. i. recogni-zable sets of finite graphs. Information and computation, 85(1) :12–75,1990.

[24] Fabien de Montgolfier, Mauricio Soto, and Laurent Viennot. Treewidthand hyperbolicity of the internet. In Network Computing and Appli-cations (NCA), 2011 10th IEEE International Symposium on, pages25–32. IEEE, 2011.

[25] Jean De Rumeur. Communications dans les reseaux de processeurs.Masson, 1994.

[26] Reinhard Diestel. Graph theory, gtm 173, 2005.

[27] Yon Dourisboure and Cyril Gavoille. Tree-decompositions with bags ofsmall diameter. Discrete Mathematics, 307(16) :2008–2029, 2007.

[28] A. Dress, K. Huber, J. Koolen, V. Moulton, and A. Spillner. BasicPhylogenetic Combinatorics. Cambridge University Press, 2012.

[29] R. Duan and S. Pettie. Fast algorithms for (max, min)-matrix multi-plication and bottleneck shortest paths. In C. Mathieu, editor, SODA,pages 384–391, New York, NY, USA, January 2009. SIAM.

22

[30] David Eppstein. Subgraph isomorphism in planar graphs and relatedproblems. In Proceedings of the sixth annual ACM-SIAM symposium onDiscrete algorithms, pages 632–640. Society for Industrial and AppliedMathematics, 1995.

[31] Wenjie Fang. On hyperbolic geometry structure of complex networks.2011.

[32] Martin Farber and Robert E Jamison. On local convexity in graphs.Discrete Mathematics, 66(3) :231–247, 1987.

[33] H. Fournier, A. Ismail, and A. Vigneron. Computing the Gromov hyper-bolicity of a discrete metric space. Technical Report arXiv :1210.3323,ArXiv, October 2012.

[34] Greg N Frederickson. Planar graph decomposition and all pairs shortestpaths. Journal of the ACM (JACM), 38(1) :162–204, 1991.

[35] Cyril Gavoille and Olivier Ly. Distance labeling in hyperbolic graphs.In Algorithms and Computation, pages 1071–1079. Springer, 2005.

[36] Fanica Gavril. Algorithms on clique separable graphs. Discrete Mathe-matics, 19(2) :159–165, 1977.

[37] Mauricio Abel Soto Gomez. Quelques proprietes topologiques desgraphes et applications a internet et aux reseaux. PhD thesis, 2011.

[38] M. Gromov. Hyperbolic groups. Essays in Group Theory, 8 :75–263,1987.

[39] Johann Hagauer and Sandi Klavzar. Clique-gated graphs. DiscreteMathematics, 161(1) :143–149, 1996.

[40] John E. Hopcroft and Robert Endre Tarjan. Dividing a graph intotriconnected components. SIAM Journal on Computing, 2(3) :135–158,1973.

[41] Edward Howorka. On metric properties of certain clique graphs. Jour-nal of Combinatorial Theory, Series B, 27(1) :67–74, 1979.

[42] E. Jonckheere and P. Lohsoonthorn. A hyperbolic geometric approachto multipath routing. Conference on Control and Automation, 2002.

[43] Edmond Jonckheere and Poonsuk Lohsoonthorn. Geometry of networksecurity. In American Control Conference, 2004. Proceedings of the2004, volume 2, pages 976–981. IEEE, 2004.

[44] Dimitris J Kavvadias, Grammati E Pantziou, Paul G Spirakis, andChristos D Zaroliagis. Hammock-on-ears decomposition : A techniquefor the efficient parallel solution of shortest paths and other problems.Theoretical Computer Science, 168(1) :121–154, 1996.

23

[45] W Sean Kennedy, Onuttom Narayan, and Iraj Saniee. On the hyper-bolicity of large-scale networks. arXiv preprint arXiv :1307.0031, 2013.

[46] J. H. Koolen and V. Moulton. Hyperbolic bridged graphs. Eur. J.Comb., 23(6) :683–699, 2002.

[47] Adrian Kosowski, Bi Li, Nicolas Nisse, and Karol Suchan. k-chordalgraphs : From cops and robber to compact routing via treewidth. In Au-tomata, Languages, and Programming, pages 610–622. Springer, 2012.

[48] Pierre de La Harpe and Etienne Ghys. Sur les groupes hyperboliquesd’apres Mikhael Gromov. 1990.

[49] Renu Laskar and Douglas Shier. On powers and centers of chordalgraphs. Discrete Applied Mathematics, 6(2) :139–147, 1983.

[50] Hanns-Georg Leimer. Optimal decomposition by clique separators. Dis-crete Mathematics, 113(1) :99–123, 1993.

[51] Daniel Lokshtanov. Finding the longest isometric cycle in a graph.Discrete Applied Mathematics, 157(12) :2670–2674, 2009.

[52] Scott McCullough. 2-chordal graphs. In Contributions to OperatorTheory and its Applications, pages 143–192. Springer, 1988.

[53] J. Michel, J. M. Rodrıguez, J. M. Sigarreta, and M. Villeta. Hyperbo-licity and parameters of graphs. Ars Combinatoria, 100 :43–63, 2011.

[54] Malte Muller. Connected tree-width. arXiv preprint arXiv :1211.7353,2012.

[55] O. Narayan and I. Saniee. The Large Scale Curvature of Networks.ArXiv e-prints, July 2009.

[56] Kenichi Oshika. Discrete Groups., volume 207. AMS Bookstore, 2002.

[57] F. Papadopoulos, D. Krioukov, M. Boguna, and A. Vahdat. Greedyforwarding in scale-free networks embedded in hyperbolic metric spaces.SIGMETRICS Performance Evaluation Review, 37(2) :15–17, 2009.

[58] Ana Portilla, Jose M Rodrıguez, and Eva Tourıs. Gromov hyperbolicitythrough decomposition of metrics spaces ii. The Journal of GeometricAnalysis, 14(1) :123–149, 2004.

[59] Neil Robertson, Paul Seymour, and Robin Thomas. Quickly excludinga planar graph. Journal of Combinatorial Theory, Series B, 62(2) :323–348, 1994.

[60] Jose M Rodrıguez and Eva Tourıs. Gromov hyperbolicity through de-composition of metric spaces. Acta Mathematica Hungarica, 103(1-2) :107–138, 2004.

24

[61] Jose M Rodrıguez and Eva Tourıs. Gromov hyperbolicity of riemannsurfaces. Acta Mathematica Sinica, English Series, 23(2) :209–228,2007.

[62] Donald J Rose. Triangulated graphs and the elimination process. Jour-nal of Mathematical Analysis and Applications, 32(3) :597–609, 1970.

[63] Petra Scheffler. A linear algorithm for the pathwidth of trees. In Topicsin combinatorics and graph theory, pages 613–620. Springer, 1990.

[64] Raimund Seidel. On the all-pairs-shortest-path problem in unweigh-ted undirected graphs. Journal of Computer and System Sciences,51(3) :400–403, 1995.

[65] Valeriu P Soltan and Vo D Chepoi. Conditions for invariance of setdiameters under d-convexification in a graph. Cybernetics and SystemsAnalysis, 19(6) :750–756, 1983.

[66] Jeremy P Spinrad. Finding large holes. Information Processing Letters,39(4) :227–229, 1991.

[67] Roberto Tamassia and Ioannis G Tollis. Planar grid embedding in lineartime. Circuits and Systems, IEEE Transactions on, 36(9) :1230–1234,1989.

[68] R. E. Tarjan. Decomposition by clique separators. Discrete Mathema-tics, 55(2) :221 – 232, 1985.

[69] Carsten Thomassen. Kuratowski’s theorem. Journal of Graph Theory,5(3) :225–241, 1981.

[70] Eva Tourıs. Graphs and gromov hyperbolicity of non-constant negati-vely curved surfaces. Journal of Mathematical Analysis and Applica-tions, 380(2) :865–881, 2011.

[71] Ryuhei Uehara. Tractable and intractable problems on generalizedchordal graphs. IEIC Technical Report (Institute of Electronics, In-formation and Communication Engineers), 98(685) :1–8, 1999.

[72] Y. Wu and C. Zhang. Hyperbolicity and chordality of a graph. Electr.J. Comb., 18(1), 2011.

A Complements a la Section 3

A.1 Preuves pour la Section 3.1

Comme annonce dans la Section 3.1, nous nous proposons de caracterisersous quelles conditions necessaires l’hyperbolicite δ(G) est uniquement at-teinte par un quadruplet de type (a|b1, b2, b3). En d’autres termes, nous

25

etudions sous quelles conditions notre algorithme de la Section 3.1 induitune erreur additive sur la valeur de l’hyperbolicite, puis nous majorons cetteerreur.

Il est utile pour la suite d’observer que, lorsqu’on mesure les distancesd’un sommet u aux sommets X dans une clique, alors on trouve au plusdeux distances differentes : soit la distance minimale d(u,X), soit la distanced(u,X) + 1. Aussi :

Lemme 17. Etant donne un quadruplet de type (a|b1, b2, b3), pour tout i ∈1, 2, 3 soit xi ∈ X sur un plus court chemin entre a et bi, et soit m =d(a,X). Si nous ajoutons dans G un nouveau sommet va, avec une areteentre va et chacun des x ∈ X tels que d(a, x) = m, alors δ(a, b1, b2, b3) =δ(va, b1, b2, b3).

Demonstration. Comme X est une clique, d(a, xi) ∈ m,m+1 est satisfaitpour n’importe quel i. En consequence, d(a, bi)+d(bj , bk) = (m+d(va, bi)−1)+d(bj , bk), ou j, k = 1, 2, 3 \ i, ce qui prouve le resultat annonce.

Ce lemme ci-dessus nous indique que nous pouvons restreindre notreetude aux plus courts chemins entre a et bi qui empruntent un sommet de Xa distance exactement d(a,X) de a. Une fois cette condition imposee, d(a,X)ne joue plus aucun role dans le calcul de δ(a, b1, b2, b3). Par consequent :

Claim 1. Nous pouvons supposer tous les sommets de A adjacents a unsommet de X.

Dans la suite, on ecrira toujours Si pour la somme d(a, bi) + d(bj , bj),avec j, k = 1, 2, 3 \ i.

Poussons plus loin notre diminution des cas a considerer. Bien qu’il puisseadvenir qu’aucun voisin de a dans X (au sens de la reduction du Lemme 17)soit a la fois emprunte par un plus court chemin entre a et bi et par unautre plus court chemin entre a et bj (pour i 6= j), nous montrerons avec leLemme 18 qu’un cas pareil n’a pas besoin d’etre pris en compte pour notrecaracterisation.

Lemme 18. Soit X une (A|B)-clique separatrice de G.Etant donne un quadruplet du type (a|b1, b2, b3), supposons sans perte degeneralite S1 ≥ S2 ≥ S3.Soit x2 ∈ X tel que d(a, b2) = d(a, x2) + d(x2, b2) et d(a, x2) = d(a,X).

Si δ(a, b1, b2, b3) ≥ δ(x2, b1, b2, b3) + 1/2, alors S1 > S2 = S3.En outre, l’inegalite ci-dessus entraıne d(a, b1) = d(a, x2) + d(x2, b1).

26

Demonstration. Rappelons que d’apres le Lemme 17, il existe x1, x2, x3 ∈ Xtel que, pour tout i = 1, 2, 3 : d(a, bi) = d(a, xi) + d(xi, bi),et sans perte de generalite d’apres le Claim 1 : d(a, xi) = d(a,X) = 1.

Soit εi = d(x2, bi)− d(xi, bi), i = 1, 2, 3.Observons que εi ∈ 0, 1,et εi = 0 si, et seulement si, x2 est sur un plus court chemin entre a et bi.En particulier, on a que ε2 = 0.

Nous pouvons reecrire d(a, bi) = d(x2, bi) + 1− εiet ainsi, Si = d(a, bi) + d(bj , bk)= d(x2, bi) + d(bj , bk) + 1− εi= S′i + 1− εi,avec j, k = 1, 2, 3 \ i, et S′1, S

′2, S′3 les trois sommes obtenues depuis

S1, S2, S3 en substituant a par x2.En d’autres termes, S′1, S

′2, S′3 sont les trois sommes necessaires au calcul de

δ(x2, b1, b2, b3).Puisque nous supposons ici

S1 ≥ S2 ≥ S3 et δ(a, b1, b2, b3) > 0,nous obtenons que S′1 = maxi=1,2,3 S

′i.

Plus precisement :– Si S′2 ≥ S′3, alors δ(a, b1, b2, b3) = δ(x2, b1, b2, b3)−ε1/2 ≤ δ(x2, b1, b2, b3).– Si S′3 > S′2, alors ε3 = 1 car S2 ≥ S3, ce qui implique S2 = S3.

Ceci, en retour, entraıne que δ(x2, b1, b2, b3) = (S′1 − S′3)/2= (S1 − 1 + ε1 − S3)/2= (S1 − S2)/2− (1− ε1)/2= δ(a, b1, b2, b3)− (1− ε1)/2≤ δ(a, b1, b2, b3).

Le Lemme 18 prouve ainsi que, pour n’importe quel quadruplet de type(a|b1, b2, b3) : soit il existe deux indices distincts i, j ∈ 1, 2, 3 et un sommetx ∈ X qui est a la fois emprunte par un plus court chemin entre a et bi etpar un autre plus court chemin entre a et bj , ou bien la valeur δ(a, b1, b2, b3)est majoree par δ(G[B∪X]). En outre, comme la condition necessaire sur lestrois sommes implique S2 = S3, il vient que le raisonnement du Lemme 18s’applique aussi au sommet b3 et a x3. Ce dont on deduit que pour tousles quadruplets du type (a|b1, b2, b3) qui sont potentiellement a prendre encompte pour la valeur de l’hyperbolicite, on peut toujours trouver un sous-ensemble de taille deux de la clique-separatrice X (voisin de a au sens dela reduction du Lemme 17), de sorte qu’il existe toujours un plus courtchemin entre a et n’importe quel bi, i = 1, 2, 3, qui passe par un de ces deux

27

sommets. Par ailleurs, un et un seul des bi doit etre a egale distance desdeux sommets de cette sous-clique.

Finalement, nous terminons cette section en mettant a profit les resultatsprecedents, et nous montrons que la contribution de tout quadruplet detype (a|b1, b2, b3) peut etre bornee superieurement de meme, a une constanteadditive pres. Plus precisement, le Lemme 19 montre que δ(a, b1, b2, b3) ≤δ(G[B ∪X]) + 1/2 :

Lemme 19. Soit X une (A|B)-clique separatrice de G,et soit x ∈ X tel que d(a, x) = d(a,X).On a que δ(a, b1, b2, b3) ≤ δ(x, b1, b2, b3) + 1/2.

Demonstration. Rappelons que nous pouvons supposer sans perte de generalited(a,X) = 1 (cf. la reduction plus haut). Dans une telle situation, tous les b ∈B satisfont d(x, b) ≤ d(a, b) ≤ d(x, b) + 1. En consequence, tous les tripletsb1, b2, b3 ∈ B satisfont de meme (d(a, b1) + d(b2, b3) −d(a, b2)− d(b1, b3)) /2≤ 1/2 + (d(x, b1) + d(b2, b3)− d(x, b2)− d(b1, b3)) /2.

La Section 3 donne une construction qui prouve que la borne superieureest atteinte.

A.2 Preuves pour la Section 3.2

Cette Section est devolue a la preuve du Theoreme 10. On rappellebrievement les outils dont nous disposons grace a la Section precedente.

Nous avons prouve avec le Lemme 19 que lorsque X est une (A|B)-cliqueseparatrice de G, et quand x ∈ X est a distance d(a,X) du sommet a ∈ A,alors δ(a, b1, b2, b3) ≤ δ(x, b1, b2, b3) + 1/2.

Rappelons que nous pouvons aussi supposer sans risque que d(a,X) = 1d’apres le Lemme 17.

Nous prouverons a present que si a, b, c, d ∈ V appartiennent a des atomesdifferents de la decomposition, et que tous les chemins entre eux passent parles sommets d’un atome A, alors δ(a, b, c, d) ≤ δ(G[A])+1.

Puisque δ(G) est un parametre positif, tout quadruplet a, b, c, d tel queδ(a, b, c, d) ≤ 1 satisfait trivialement δ(a, b, c, d) ≤ δ(G[A]) + 1 pour n’im-porte quel atome A arbitrairement choisi. Par consequent, nous ne nousinteresserons dans cette Section qu’aux proprietes des quadruplets a, b, c, dtels que δ(a, b, c, d) > 1, ce qui est equivalent a δ(a, b, c, d) ≥ 3

2 . La localisa-tion de ces quadruplets s’avere utile pour un calcul aussi efficace que possiblede δ(G).

28

Nous commencerons par deux proprietes structurelles tres simples, quedoivent necessairement satisfaire de tels quadruplets, et qui permettront desimplifier les preuves a venir.

Claim 2. Soit δ(a, b, c, d) ≥ 3/2, et soit X une clique-separatrice pour G.Alors on a : |X ∩ a, b, c, d| ≤ 1.

Demonstration. Par l’absurde. Sans perte de generalite supposons a, b ∈X. D’apres le Lemme 5 on a δ(a, b, c, d) ≤ d(a, b) ≤ 1, ce qui contreditδ(a, b, c, d) ≥ 3/2.

Claim 3. Soit δ(a, b, c, d) ≥ 3/2, et soit X une clique-separatrice pour G.Alors il existe une composante connexe C de G\X telle que |C∩a, b, c, d| ≥ 3.

Demonstration. D’apres le Claim 2,X contient au plus un element de a, b, c, d.Deux cas sont a present a distinguer :

Si |X ∩ a, b, c, d | = 1, alors aucune composante connexe C de G\Xne peut contenir exactement un element de a, b, c, d, puisque sinon leLemme 9 pourrait etre applique a C ∪X et V \C. Par consequent, il existeune composante contenant les trois elements restants.

Si |X∩a, b, c, d | = 0, alors en raison du Lemme 9 et comme precedemment,aucune composante connexe C de G\X ne peut contenir exactement deuxelements de a, b, c, d. De meme, si deux d’entre elles, appelons-les C,C ′,contiennent exactement un element de a, b, c, d, alors le Lemme 9 pourraitetre applique a C ∪ C ′ ∪ X et V \(C ∪ C ′), ce qui entraınerait ici encoreδ(a, b, c, d) ≤ 1. Ainsi, il doit exister une composante connexe C de G\Xtelle que |C ∩ a, b, c, d | ≥ 3.

Nous nous attarderons quelques instants sur une autre propriete elementaire,mais essentielle, qui est celle selon laquelle les sommets dans une clique nepeuvent pas etre separes pendant la clique-decomposition. En effet, on ob-serve qu’etant donnees deux cliques X1, X2, avec X2 une clique-separatrice,alors ou bien X1 ⊆ X2, ou bien il existe une unique composante connexe Cde G\X2 telle que X1 \X2 ⊆ C. Cette propriete de non-separation s’avereracruciale dans les preuves qui suivent. Rappelons egalement que, dans le se-cond cas (i.e. X1 \ X2 ⊆ C), nous disons que les sommets de V \(C ∪ X2)sont separes de X1 par X2.

Le coeur du reste de la preuve consiste a present a montrer :– d’une part, que si l’erreur pour notre algorithme de la Section 3.1 est

d’au moins 1 sur la valeur de l’hyperbolicite, alors les quatre sommetsde n’importe quel quadruplet maximal doivent etre dans quatre atomesdifferents (trois atomes ne suffisent pas) ;

29

Fig. 5: Une illustration du Lemme 20.

– d’autre part, qu’il ne joue en rien, sur la valeur de l’hyperbolicite,qu’un sommet dans un quadruplet maximal soit separe des autres parune seule clique-separatrice ou par au moins deux cliques-separatricesdistinctes.

Pour ce qui est du premier point, nous avons deja montre avec le Lemme 19que lorsqu’il existe une (a|b, c, d)-clique separatriceXa, on a toujours δ(a, b, c, d) ≤δ(xa, b, c, d) + 1/2, avec xa ∈ Xa un voisin de a (au sens de la reduction duLemme 17). Dans un premier temps, nous allons renforcer ce resultat :

Lemme 20. Soit δ(a, b, c, d) ≥ 3/2.Supposons l’existence de deux cliques-separatrices Xa, Xd dans G telles que :

– Xa separe a de b, c, d ;– et Xd separe d de a, b, c.

Alors on peut trouver xa ∈ Xa, xd ∈ Xd tels que :δ(a, b, c, d) ≤ δ(xa, b, c, xd) + 1/2.

Demonstration. Nous convenons dans la suite que T1, T2, T3 = S1, S2, S3avec T1 ≥ T2 ≥ T3 et S1, S2, S3 les trois sommes associees au calcul deδ(a, b, c, d). S’il existe un sommet xa ∈ Xa tel que δ(a, b, c, d) ≤ δ(xa, b, c, d),alors par le Lemme 19 on obtient un sommet xd qui satisfait l’enonce duLemme.Sinon, soit T2 = d(a, u2) + d(u1, u3), avec u1, u2, u3 = b, c, d,et choisissons un sommet xa ∈ Xa tel que d(a, u2) = d(a, xa) + d(xa, u2) etd(a, xa) = d(a,Xa).Nous rappelons qu’un tel sommet xa existe toujours d’apres le Lemme 17,et que nous pouvons supposer d(a,Xa) = 1 d’apres le Claim 1.

Comme δ(a, b, c, d) ≥ δ(xa, b, c, d) + 1/2 par hypothese, nous obtenonsque :

30

δ(a, b, c, d) = δ(xa, b, c, d) + 1/2 d’apres les Lemmes 17 et 19,et que T1 > T2 = T3 d’apres le Lemme 18.

Soient T ′1, T′2, T

′3 les trois sommes obtenues depuis T1, T2, T3 par la substi-

tution de a par xa ; en d’autres termes, ce sont les trois sommes necessairesau calcul de δ(xa, b, c, d).D’apres le Lemme 18 il vient que :d(a, u1) = d(a, xa) + d(xa, u1) = 1 + d(xa, u1)et ainsi, T ′1 = T1 − 1, T ′2 = T2 − 1.De plus, puisque T3 = T2 et δ(a, b, c, d) = δ(xa, b, c, d) + 1/2, nous avonsegalement T ′3 = T3.Ce resultat implique T ′1 ≥ T ′3 > T ′2.Par ailleurs, rappelons que a, b, c ne sont pas separes par Xd d’apres leClaim 3. En consequence, Xa n’est pas separee de a, b, c par Xd non plus.D’apres le Lemme 18, comme la contrainte T ′1 > T ′3 = T ′2 n’est pas satisfaite,donc il existe xd ∈ Xd tel que δ(xa, b, c, d) ≤ δ(xa, b, c, xd).

En d’autres termes, deux substitutions consecutives de sommets distinctsdans le quadruplet a, b, c, d ne diminuent pas la valeur initiale δ(a, b, c, d)pour l’hyperbolicite de plus que 1/2. Pour completer ce resultat, il nousreste encore a prouver que, si une diminution est reellement obtenue par lasubstitution du sommet u ∈ a, b, c, d, alors substituer a son tour le sommetu′ remplacant u n’aggrave pas cette diminution. En d’autres termes, nouspourrons supposer que chaque sommet u du quadruplet est substitue au plusune fois. Afin de le prouver, nous presenterons dans la suite une methodequi relie au quadruplet a, b, c, d un atome A de la clique-decomposition.

Claim 4. Supposons qu’il existe une clique X qui separe a de b, c, d. Alorsil existe une clique Xa minimale pour l’inclusion qui verifie cette propriete,et telle que pour toute clique X ′, il existe un sommet dans b, c, d qui n’estpas separe de Xa par X ′.

Demonstration. D’abord, il est a noter que la contrainte de minimalite pourl’inclusion n’a pas a etre verifiee dans la preuve : en effet, si le reste desconditions sont satisfaites par une clique donnee, alors la minimalite parinclusion pourra s’obtenir en ne considerant qu’une sous-clique de celle-ci.

La preuve se fait par recurrence. Pour le cas de base, soit X0 une cliquequi separe a de b, c, d et qui est minimale au sens de l’inclusion pour cettepropriete. Une telle clique peut etre obtenue avec un sous-ensemble de laclique X de l’enonce.

Par recurrence, supposons que pour i ≥ 0 on a pu construire une sequencede cliques deux-a-deux differentes, notees X0, . . . , Xi et telles que, pour tout

31

j = 0 . . . i, Xj separe b, c, d de a,X0, . . . , Xj−1, et elle est minimale pourl’inclusion pour cette propriete.

Si Xi ne peut pas etre separee de b, c, d par l’utilisation d’une clique-separatrice la preuve est terminee.Sinon, soit X ′ une clique-separatrice qui separe b, c, d de Xi et qui est mini-male pour l’inclusion pour cette propriete.Clairement, on a que X ′ 6= Xi.Nous pretendons a present que X ′ 6= Xj pour tout j < i.La preuve se fait par l’absurde.Supposons X ′ = Xj pour un certain j < i.D’apres l’hypothese de recurrence, tous les chemins entre b, c, d et Xj\Xi

passent par Xi et donc, puisque Xj separe b, c, d de Xi, nous obtenons queXi ∩Xj 6= ∅. Mais alors il vient que tous les chemins entre b, c, d et Xi\Xj

passent par Xi ∩Xj , c’est-a-dire Xi = Xi ∩Xj par minimalite de Xi. Cecientraıne Xi ⊆ Xj = X ′, ce qui est une contradiction.Nous pouvons prouver de meme que a /∈ X ′. Par consequent, on peut choisirXi+1 = X ′.

Finalement, le resultat du Claim 4 tient a ce que le nombre de cliquespossibles est fini.

Cette propriete du Claim 4 a pour objectif d’etendre la propriete denon-separabilite d’une unique clique a plusieurs cliques a la fois. Nous leformalisons dans le lemme suivant :

Lemme 21. Soit δ(a, b, c, d) ≥ 3/2. Supposons qu’il existe deux cliques-separatrices Xa et Xd dans G telles que :

– Xa separe a de b, c, d ;– Xd separe d de a, b, c ;– Xa et Xd satisfont toutes deux la condition du Claim 4.

Alors, pour toute clique-separatrice X, il existe une composante connexe Cde G\X telle que Xa, Xd ⊆ C ∪X.

Demonstration. Par l’absurde. Supposons qu’il existe X telle que Xa et Xd

sont separees par X. Nous distinguerons deux cas.D’abord, si X ∩ a, d 6= ∅, alors sans perte de generalite nous suppo-

serons que a ∈ X. En particulier, on a que b, c, d /∈ X d’apres le Claim 2.Par consequent, les sommets b, c, d sont dans la meme composante connexede G \ X d’apres le Claim 3. Cela entraıne que Xa \ X est dans la memecomposante que b, c, d d’apres le Claim 4. Or, Xd \ X est egalement danscette composante, comme consequence directe de ce que b et c, d ne sont

32

a

b

c d

a’

b’

c’ d’

Fig. 6: Une illustration du Corollaire 24.

pas separes par X. D’ou finalement, on obtient que Xa et Xd ne sont passepares par X, ce qui est une contradiction.

Dans un second temps, nous supposons que X ∩ a, d = ∅. Puisque Xest un (Xa|Xd)-separateur par hypothese, il vient que X separe les sommetsa et d. Mais alors, d’apres le Claim 3, nous pouvons supposer sans pertede generalite que X separe les sommets b, c, d de a. Et nous nous ramenonsalors au cas precedent.

Afin de conclure quant a notre propriete etendue de non-separabilite, leLemme 21 aura besoin d’etre renforce dans la suite. Nous l’utiliserons avecla Propriete de Helly :

Lemme 22. Soit Xi, i = 1..k, une collection de cliques. Supposons quepour toute clique-separatrice X et pour tout i 6= j, il existe une composanteconnexe C de G\X telle que Xi, Xj ⊆ C ∪X. Alors il existe un atome A telque

⋃ki=1Xi ⊆ A.

Demonstration. Quitte a simuler de maniere gloutonne la clique-decompositionde G, on observera qu’il suffit de montrer que, pour toute clique-separatriceX, on peut trouver une composante connexe C de G\X telle que

⋃ki=1Xi ⊆

C∪X. Aussi pouvons-nous ignorer sans risque tous les Xi qui sont contenusdans X. Soient Xi, Xj deux cliques qui ne sont pas contenues dans X. Parla propriete de non-separabilite, on a qu’il existe une unique composanteconnexe Ci (resp. Cj) de G \X telle que Xi ⊆ Ci ∪X (resp. Xj ⊆ Cj ∪X).Puisque par hypothese, il existe au moins une composante connexe C deG\X telle que Xi, Xj ⊆ C ∪ X, nous pouvons finalement conclure queC = Ci = Cj .

Nous sommes a present en mesure de rassembler nos resultats dans le Co-rollaire 23 avant de conclure, avec le Corollaire 24, la preuve du Theoreme 10.

33

Corollaire 23. Soit δ(a, b, c, d) ≥ 3/2. Etant donnee la decomposition dugraphe G selon ses cliques-separatrices minimales, il existe un atome A telque, pour tout sommet u ∈ a, b, c, d, ou bien u ∈ A ou bien il existe uneclique-separatrice Xu ⊆ A qui separe u de a, b, c, d \ u.

Demonstration. Si le quadruplet a, b, c, d est contenu dans le meme atome A,alors il n’y a rien a faire. Donc nous supposerons dans la suite l’existence d’unsommet u et d’une clique-separatrice associee Xu qui satisfait la condition duClaim 4. D’apres le Lemme 21, pour tout sommet v ∈ a, b, c, d \ u, nouspouvons associer a v une clique-separatrice Xv inseparable de Xu, pourvuque v puisse etre separe des trois autres sommets. Considerons, au contraire,un sommet v qui ne peut pas etre separe de a, b, c, d \ v par une clique.Par l’absurde, supposons qu’il existe une clique-separatrice X qui separe vde Xu.

Tout d’abord, si u ∈ X alors on a que a, b, c, d \ u est dans une uniquecomposante connexe de G\X d’apres le Claim 3. En particulier, Xu n’estpas separe de a, b, c, d \ u d’apres le Claim 4. C’est une contradiction.

Deuxiemement, si u /∈ X, alors il vient directement que X separe v de uet ainsi, X separe u de a, b, c, d \ u d’apres le Claim 3. A nouveau, Xu

n’est pas separe de a, b, c, d \ u d’apres le Claim 4. Une contradiction.Par consequent, le sommet v ne peut pas etre separe de Xu dans ce cas-

la. Partant du principe qu’un unique sommet est un exemple trivial de clique(de taille 1), nous pouvons finalement conclure en appliquant la Proprietede Helly du Lemme 22.

Corollaire 24. Soit δ(a, b, c, d) ≥ 32 . Etant donnee la decomposition de

G selon ses cliques-separatrices minimales, il existe un atome A tel queδ(a, b, c, d) ≤ δ(G[A]) + 1.

Demonstration. Choisissons A tel qu’il est defini dans le Corollaire 23. Nousprocedons comme suit. Pour tout sommet u ∈ a, b, c, d, si u est deja dansA alors nous le gardons. Sinon, d’apres le Corollaire 23 il existe une clique-separatrice Xu ⊂ A qui separe u de a, b, c, d \ u, et nous substituonsu par un sommet xu ∈ Xu (choisi selon des contraintes que nous allonsdeterminer dans la suite). Soit a′, b′, c′, d′ le quadruplet qu’on obtient. Il suffita present d’appliquer le Lemme 20 au plus deux fois, (par exemple) une foispour choisir a′, b′ et une autre fois pour choisir c′, d′, ce qui nous permet detrouver un quadruplet a′, b′, c′, d′ tel que δ(a, b, c, d) ≤ δ(a′, b′, c′, d′) + 2 ×(1/2) = δ(a′, b′, c′, d′) + 1.

A nouveau, cette borne est la meilleure possible, comme le montre l’exemplede la Fig. 7, et nous avons prouve ce faisant le Theoreme 10.

34

Fig. 7: Le graphe sur la gauche a pour hyperbolicite 1. L’addition des tri-angles (sur la droite) augmente la valeur de l’hyperbolicite de 1.

A.3 Preuves pour la Section 3.3

Grace aux preuves des Sections A.1 et A.2, nous pouvons maintenant for-maliser la notion de substitut des atomes, dont nous avions donne l’intuitiondans la Section 3.3. Pour ce faire, nous procederons en deux etapes.

D’abord, etant donnee une (unique) clique-separatriceX, nous consideronschaque composante connexe B deG[V \X] separement. Pour chacune d’entreelles, on se contente d’appliquer la reduction du Lemme 17 : chaque fois qu’ilexiste (au moins) un sommet a /∈ B ∪X tels que les sommets dans X ′ ⊆ Xsont ceux a distance d(a,X) de a dans X, nous ajoutons dans G[B ∪X] unsommet vX′ qui est seulement adjacent aux sommets dans X ′. Dans le piredes cas, on ajoute donc |V \ (B ∪X)| sommets. Ce qui montre bien que lenombre de sommets ne peut que decroıtre (quand il est compare au grapheG original). Nous noterons B∗ la modification de G[B ∪X] qui en resulte,et nous l’appellerons le substitut de B dans la suite.

Claim 5. Soit G = (V,E) un graphe biconnexe tel que δ(G) ≥ 1, et soitX une clique-separatrice pour G. Soient aussi B1, . . . , Bk les composantesconnexes de G[V \X]. Alors δ(G) = max1≤i≤k1, δ(B∗i ).

Demonstration. Par construction, pour tout 1 ≤ i ≤ k, l’inegalite δ(B∗i ) ≥δ(G[Bi ∪X]) est triviale. Par ailleurs d’apres le Lemme 17, la valeur δ(B∗i )est minoree par le maximum pris sur tous les δ(a, b1, b2, b3), ou a /∈ Bi etb1, b2, b3 ∈ Bi. Nous rappelons que les quadruplets du type (a1, a2|b1, b2)n’ont aucune influence sur le resultat final d’apres le Lemme 9. Il s’ensuitdonc que δ(G) ≤ max1≤i≤k1, δ(B∗i ).

De plus, le Lemme 9 prouve egalement que pour tout X1, X2 ⊆ X etpour tout b1, b2 ∈ V (B∗i ), on a que δ(b1, b2, vX1 , vX2) ≤ 1, puisque X est un(b1, b2|vX1 , vX2)-separateur dans B∗i . En consequence, notre construction necree pas de quadruplets dont l’hyperbolicite est plus grande que δ(G).

35

X1

X2

X3

X4

A

Fig. 8: Le substitut d’un atome.

Montrons a present comment notre construction peut etre generaliseeaux atomes A. Comme indique dans la Section 3.3 nous avons besoin, pource faire, de connaıtre les cliques-separatrices minimales qui ont ete utiliseespendant la decomposition. Les algorithmes proposes dans [50, 68] nous lepermettent sans avoir a payer de surcout. Soit X une clique-separatrice mi-nimale de la decomposition, contenue dans A. Nous noterons BX le substitutde la composante connexe de G[V \X] qui contient A \X. Le substitut A∗

de A s’obtient finalement comme l’union de tous les substituts B∗X , ou Xest une clique-separatrice minimale de la decomposition contenue dans A,moins les sommets dans V \A (voir la Figure 8).

Claim 6. Soit G = (V,E) un graphe biconnexe tel que δ(G) ≥ 1, et soientA1, . . . , Ak les atomes de G. Alors δ(G) = max1≤i≤k1, δ(A∗i ).

Demonstration. Soient a, b, c, d tels que δ(a, b, c, d) ≥ 3/2. D’apres le Corol-laire 23, il existe un atome A tel que, pour tout sommet u ∈ a, b, c, d, oubien u ∈ A ou bien il existe une clique-separatrice Xu ⊆ A qui separe ude a, b, c, d \ u. Nous considerons a present le quadruplet a∗, b∗, c∗, d∗

de A∗ que nous definissons comme suit. D’abord, pour chaque sommetu ∈ a, b, c, d qui est contenu dans A, nous selectionnons u∗ = u. Dansun second temps, si u /∈ A, alors nous considerons une clique-separatriceminimale X ′u ⊆ A, utilisee par l’algorithme de decomposition, et qui separeu de A. Dans ce cas-la, nous prenons u∗ = vX∗u , ou X∗u ⊆ X ′u represente lessommets dans X ′u qui sont a distance d(u,X ′u) de u. D’apres le Lemme 17et le Claim 3, il s’ensuit que δ(A∗) ≥ δ(a∗, b∗, c∗, d∗) = δ(a, b, c, d). Donc,l’inegalite δ(G) ≤ max1≤i≤k1, δ(A∗i ) est satisfaite.

L’autre direction, qui sert a prouver qu’aucun quadruplet d’un substi-

36

tut n’a une valeur plus grande que δ(G) pour son hyperbolicite, peut etredemontree d’une maniere quasiment similaire a ce qui a ete fait pour leClaim 5.

A.4 Complements pour la Discussion

Nous avons explique dans la Section 3.4 pourquoi notre travail ne s’etendaitpas aux decompositions par des separateurs de plus large diametre que 1,meme si les separateurs employes sont isometriques. Le contre-exemple pro-pose etait celui des graphes pontes, qui sont completement decomposablespar cette methode, mais dont l’hyperbolicite peut etre arbitrairement grande.Ce resultat est d’autant plus decevant que pour les graphes cop-wins, dontles graphes pontes font partie, la suppression d’un sommet domine du graphe(ou coin) a des effets comparables sur l’hyperbolicite du graphe a ceux d’unsommet simplicial (cas particulier pris en compte par notre decomposition) :

Claim 7. Soit G = (V,E) un graphe connexe, et soient x, y ∈ V tels queN(x ∪ x ⊆ N(y) ∪ y (le sommet x est domine par le sommet y). Alors,pour tout b1, b2, b3 ∈ V \ x, on a que δ(x, b1, b2, b3) ≤ δ(y, b1, b2, b3) + 1/2.D’ou : δ(G \ x) ≤ δ(G) ≤ δ(G \ x) + 1/2.

Demonstration. D’abord, puisque x est domine par y, il vient que G \ xest isometrique. Par ailleurs, pour tout b 6= x, la double-inegalite d(b, y) ≤d(b, x) ≤ d(b, y) + 1 est verifiee. Le reste de la preuve est a present similaireau Lemme 19.

Rappelons que tous les graphes cop-wins non triviaux possedent un coin,dont la suppression preserve la nature cop-win du graphe. Cela signifie qu’endepit de sa proximite evidente avec le Lemme 19, une utilisation repetee duClaim 7 pour decomposer un graphe peut conduire a une erreur arbitraire-ment importante sur la valeur reelle de l’hyperbolicite du graphe.

En revanche, la propriete plus forte de separateur gated (toujours dediametre borne) mene a une decomposition compatible avec le calcul del’hyperbolicite. Un sous-ensemble X ⊆ V est dit gated si, et seulement si,pour tout sommet v ∈ V , il existe un sommet xv ∈ X (que nous appelons laporte de v) tel que, pour tout sommet x ∈ X, xv est sur un plus court cheminentre x et v. On notera que les quadruplets du type (a|b1, b2, b3) ne jouentaucun role dans le calcul de l’hyperbolicite si le (A|B)-separateur X est gated(le sommet a peut toujours etre substitue par sa porte xa). En particulier,lorsque toutes les cliques-separatrices de notre graphe d’etude sont gated,alors notre methode de decomposition retourne toujours la valeur exacte

37

pour l’hyperbolicite (sans avoir a recourir aux substituts). Cette conditionsuffisante est verifiee pour tous les graphes clique-gated, soit une conditionencore plus forte qu’on peut reconnaıtre en temps O(nm) [39].

B Complements a la Section 4

B.1 Puissances de Graphe et Hyperbolicite

Nous commencerons cette section par des resultats sur les puissances degraphe. Ce travail etend celui dans [5], pour lequel seuls les graphes distance-hereditaires avaient ete consideres. Nous rappelons que la jeme puissanced’un graphe G = (V,E) est definie comme le graphe Gj = (V,Ej), avecEj l’ensemble des paires de sommets distincts qui sont a distance au plusj dans G. En particulier, G1 = G. On montrera dans ce qui suit que lavaleur de l’hyperbolicite δj = δ(Gj) est intrinsequement reliee a celle deδ1 = δ(G) (Proposition 25). Cette relation se deduit elle-meme des relationsqui existent entre distances dans G et distances dans Gj :

Claim 8. Soit G = (V,E) un graphe, et soit j un entier strictement positif.Pour tout u, v ∈ V , on a que : dGj (u, v) = ddG(u,v)

j e.

Demonstration. D’abord, nous rappelons qu’une arete dans Gj peut tou-jours etre remplacee dansG par un chemin de taille au plus j. D’ou l’inegalitej.dGj (u, v) ≥ dG(u, v), ce qui equivaut a ce que dGj (u, v) ≥ dG(u,v)

j . Or lesdistances dans un graphe sont des entiers, ce qui implique finalement quedGj (u, v) ≥ ddG(u,v)

j e.Reciproquement, soit n’importe quel plus court chemin P entre u et

v dans G. Pour tout i ≥ 1 tel que j.i < dG(u, v), on notera xi l’uniquesommet dans P qui est a distance j.i de u. Nous observons que P ′ =u, x1, . . . , xi, . . . , v est un chemin dans Gj entre u et v. En consequence,on a bien que : dGj (u, v) ≤ ddG(u,v)

j e.

Proposition 25. Etant donne un entier strictement positif j, soit δj =δ(Gj). On a que :δ(G)+1

j − 1 ≤ δj ≤ δ(G)−1j + 1.

Demonstration. Soit a, b, c, d ∈ V n’importe quel quadruplet dans G. Onrappelle la notation S1, S2, S3 pour les trois sommes dG(a, b) + dG(c, d),dG(a, c) + dG(b, d) et dG(a, d) + dG(b, c), qui sont a prendre en compte pourle calcul de δG(a, b, c, d). On les differenciera des sommes a considerer pourδGj (a, b, c, d), en notant ces dernieres S′1, S

′2, et S′3.

38

D’apres le Claim 8, pour tout u, v ∈ a, b, c, d on a que dGj (u, v) =ddG(u,v)

j e ; de plus, dG(u,v)j ≤ ddG(u,v)

j e ≤ dG(u,v)j +(1−1/j). En consequence,

pour tout i ∈ 1, 2, 3 on a que Si/j ≤ S′i ≤ Si/j + 2(1− 1/j).Sans perte de generalite, on suppose que S1 ≤ S2 ≤ S3. S’il existe un

i ∈ 2, 3 tel que S′i = maxS′1, S′2, S′3, alors on a que :δGj (a, b, c, d) ≤ (S′i − S′1)/2 ≤ (Si − S1)/2j + 1− 1/j ≤ 1− 1/j < 1.Sinon, on a que :δGj (a, b, c, d) ≤ (S′1−S′2)/2 ≤ (S1−S2)/2j+1−1/j = δG(a, b, c, d)/j+1−1/j.Par consequent, δGj (a, b, c, d) ≤ δG(a,b,c,d)−1

j + 1, d’ou δj ≤ δ(G)−1j + 1.

On impose a present que δG(a, b, c, d) = δ(G). Nous pouvons deja observerque l’inegalite δ(G)+1

j −1 ≤ δj est trivialement satisfaite des que j ≥ δ(G)+1,

puisque δ(G)+1j − 1 ≤ 0 dans ce cas-la. Aussi nous nous contraignons au cas

non trivial ou j est inferieur a δ(G) + 1.Par hypothese, pour tout i ∈ 2, 3 on a que : S1 ≥ Si + 2δ(G),et ainsi que : S′1 ≥ S1/j≥ Si/j + 2δ(G)/j≥ Si/j + 2(δ(G) + 1)/j − 2/j≥ Si/j + 2(1− 1/j)≥ S′i.En consequence de quoi : δGj (a, b, c, d) = (S′1 −maxS′2, S′3)/2≥ (S1/j − S2/j − 2(1− 1/j))/2= δG(a, b, c, d)/j + 1/j − 1.Ce qui revient a ce que δj ≥ δ(G)+1

j − 1 est aussi satisfait dans ce cas-la.

Un des interets de la Proposition 25 est qu’elle pourrait conduire a une4-approximation de l’hyperbolicite du graphe. En effet, si G est un grapheδ-hyperbolique, pour δ > 0, alors on a que G2δ−1 est 1-hyperbolique, puis-qu’alors δ−1

j < 1/2. Reciproquement, si Gj est 1-hyperbolique pour un en-

tier j donne, alors on a que δ(G)+1j − 1 ≤ 1 et ainsi, G doit etre (2j − 1)-

hyperbolique. Cela etant, un algorithme efficace pour les graphes d’hyper-bolicite 1 doit encore etre trouve pour que nous puissions appliquer cettemethode.

J’ai dans l’idee qu’on pourrait passer outre ce probleme, quitte a augmen-ter la constante multiplicative de l’approximation, en imposant une struc-ture plus contrainte que seulement la 1-hyperbolicite. Par exemple, un demes sujets de recherche est de determiner, en fonction de [7, 8], si quand Gest un graphe δ-hyperbolique, on peut toujours trouver un entier j = O(δ)tel que Gj soit cordal. Notons que si Gj est cordal, alors il est egalement

39

1-hyperbolique d’apres le Corollaire 11. J’etudie de meme si la variante desgraphes cop-wins exploree dans [17] pourrait contraindre suffisamment lastructure des puissances du graphe G ; les resultats qui s’y trouvent ontrecemment mene a une O(1)-approximation pour l’hyperbolicite [16], maispour une constante assez large, et qui n’exploite pas les puissances du graphe.

Nous utiliserons la Proposition 25 dans la suite sous une forme plusfaible, enoncee comme suit :

Corollaire 26. Soit G = (V,E) un graphe connexe, et soit j un entierstrictement positif. Si δ(G) ≤ 1, alors on a que : δj ≤ δ(G).

Demonstration. Si G est 0-hyperbolique, alors G est un cactus de cliquesbiconnexe, c’est-a-dire un graphe complet, et il en est de meme pour Gj .Si G est 1/2-hyperbolique, alors d’apres la Proposition 25 on a que : δj ≤1/2−1j + 1 < 1 ; donc, Gj est 1/2-hyperbolique aussi. Finalement, quand

δ(G) = 1, on a d’apres la Proposition 25 que δj ≤ 1−1j + 1 = 1.

Pourtant de celebres familles de graphes 1-hyperboliques, a l’image desgraphes cordaux, sont connues pour ne pas etre stables par passage auxpuissances du graphe [49]. Mais le Corollaire 26 raffine ce resultat : nousmontrons que les puissances des graphes cordaux, bien qu’elles puissent nepas etre cordales, sont proches de cette famille de graphes pour la valeur del’hyperbolicite.

B.2 Convexite dans les Graphes

La presente Section est une digression sur la caracterisation des graphesd’hyperbolicite 1/2 dans [3]. Celle-ci repose en fait sur deux caracterisationspartielles, toutes deux necessaires, et a elles deux suffisantes. Nous presenteronsici la premiere de ces caracterisations, sa relation avec le Theoreme 12, plusun algorithme de reconnaissance associe.

Tout d’abord, nous devons definir des notions basiques en geometriedes graphes [4]. Soit G = (V,E) un graphe quelconque. Pour tout couplede sommets u, v ∈ V , on definit l’intervalle [u, v] comme l’ensemble dessommets dans V sur un plus court chemin entre u et v. Plus formellement :[u, v] = x ∈ V : d(u, v) = d(u, x) + d(x, v). Pour chaque sommet u ∈ V , etpour tout entier positif k, nous definissons egalement la boule Bk(u) commel’ensemble des sommets qui sont a une distance au plus k de u. En d’autrestermes : Bk(u) = v ∈ V : d(u, v) ≤ k. Finalement, un sous-ensembleX ⊆ V est dit convexe si, et seulement si, pour n’importe quel couple desommets u, v ∈ X on a que [u, v] ⊆ X. Cette condition est equivalente a ce

40

que tous les plus courts chemins entre n’importe quels deux sommets dansX sont entierement contenus dans X. En particulier, V est trivialementconvexe, et si X est convexe alors necessairement G[X] est isometrique.

La relation entre la convexite dans les graphes et les graphes d’hyperbo-licite 1/2 peut s’exprimer ainsi :

Proposition 27. ( [32, 65]) Soit G = (V,E) un graphe connexe. Toutesles boules de G sont convexes si, et seulement si, tous les cycles dans G delongueur 4 ou au moins 6 sont pontes.

La Proposition 27 est donc un exemple de condition necessaire plus forteque la Condition 1. A ce titre, un algorithme de reconnaissance pour cettenouvelle condition pourrait etre employe de meme pour verifier la Condi-tion 1. La condition de la Proposition 27 est egalement necessaire pourd’autres classes de graphes que les graphes 1/2-hyperboliques (par exemple,les graphes pontes [4]). Aussi, il apparaıt interessant de developper pour elleune sous-routine.

A cette fin, commencons par reduire le probleme a celui du calcul desdistances dans un graphe :

Proposition 28. Il y a une reduction en temps quadratique du problemede decider si un sous-ensemble dans un graphe est convexe au calcul de lamatrice des distances dans un graphe.

Demonstration. Soit G = (V,E) un graphe connexe, et soit X ⊆ V . Nousconstruisons le graphe G′ = (V,E′) comme suit : Ce graphe est base sur G,dont on retire toutes les aretes aux deux extremites dans X. En d’autrestermes, E′ = u, v ∈ E : u /∈ X ou v /∈ X. On notera qu’ici, il se peutque G′ ne soit pas connexe, auquel cas on supposera infinie la distance entredeux sommets qui ne sont pas connectes.

Ce que nous pretendons est que X est convexe si, et seulement si, pourtoute paire u, v ∈ X, on a que dG(u, v) < dG′(u, v). Pour le prouver, obser-vons deja que, par construction, tous les plus courts chemins dans G′ entredeux sommets dans X sortent (au moins en partie) de X. En consequence,si X est convexe alors il est necessaire que pour tout u, v ∈ X, on a quedG(u, v) < dG′(u, v). Reciproquement, supposons X non convexe, et soit Pun plus court chemin entre deux sommets dans X qui n’est pas entierementcontenu dans X. Soit P ′ un sous-chemin maximal de P qui sort entierementde X. Par definition de P ′, les extremites de P ′ ne sont pas des extremites deP . Par consequent, on peut trouver deux sommets u, v ∈ P tels que chacund’entre eux est adjacent a une extremite de P ′. De plus, u et v appartiennent

41

... ...

u,0

x,0 y,0 z,0

v,0

s1,0

t,0

s2,0 s3,0

u,1

x,1 y,1 z,1

v,1

s1,1 s2,1 s3,1

t,1

Fig. 9: La construction du graphe Gu.

tous deux a X par maximalite de P ′. Et, comme u, P ′, v est un sous-chemind’un plus court chemin P , c’est aussi un plus court chemin. En d’autrestermes, dG′(u, v) = dG(u, v), ce qui montre la reciproque.

Finalement, afin de decider si X est convexe, nous pouvons procedercomme suit. D’abord nous calculons les distances dans G. Ensuite, nousconstruisons G′ en temps lineaire. Nous calculons les distances dans G′.Nous verifions en temps O(|X|2) que pour tout u, v ∈ X on a que dG(u, v) <dG′(u, v).

Par soucis de completer la Proposition 28, nous rappellerons que le calculdes distances dans un graphe peut etre effectue en temps O(nα) [64].

Nous terminerons cette section par un algorithme pour verifier la condi-tion de la Proposition 27 :

Theoreme 29. Soit G = (V,E) un graphe connexe. Decider si toutes lesboules de G sont convexes peut etre realise en temps O(nα+1).

Demonstration. D’abord, remarquons que, puisqu’il existeO(n2) boules dansG, le Theoreme 29 n’est pas un corollaire de la Proposition 28. En fait, ilnous faut legerement adapter la reduction de la Proposition 28, afin quenous puissions simultanement verifier la convexite d’un nombre lineaire deboules.

Nous pretendons dans ce but que, pour tout sommet u, et pour toutentier strictement positif k, si Bk−1(u) est convexe alors Bk(u) est convexesi, et seulement si, tous les plus courts chemins entre deux sommets qui sonta distance exactement k de u sont contenus dans Bk(u). La condition estclairement necessaire, comme consequence de la definition pour la convexite.Pour prouver qu’elle est suffisante, il suffit d’observer que Bk(u) \ Bk−1(u)(c’est-a-dire : tous les sommets a une distance exactement k de u) est un(Bk−1(u)|V \Bk(u))-separateur.

Pour chaque sommet u ∈ V , nous procedons a present comme suit.Nous construisons le graphe Gu = (Vu, Eu) en deux etapes. D’abord, nous

42

ajoutons un sommet v′ pour chaque sommet v du graphe. Ensuite, nousconnectons v′ a tous les voisins x du sommet v qui sont plus loin de u quene l’est v. Formellement :

– Vu = V × 0, 1 ;– Gu[V × 0] est isomorphe a G (par l’isomorphisme qui envoie (v, 0)

sur le sommet v) ;– pour chaque sommet v ∈ V on a que NGu((v, 1)) = (x, 0) ∈ V ×0 :v, x ∈ E et d(u, x) = d(u, v) + 1.

Finalement, nous verifions que pour tout k ≥ 1, et pour chaque couple desommets x, y a une distance k de u, on a que dG(x, y) < dGu((x, 1), (y, 1)).Le cout de toutes ces operations, pour un sommet donne u, est bornesuperieurement par le cout du calcul des distances dans les deux graphesG et Gu, c’est-a-dire O(nα). Comme nous devons repeter le procede pourchaque sommet du graphe, cela nous donne une complexite (au plus) n foisplus grande, soit : O(nα+1).

B.3 Preuves pour la Section 4.1

Cette Section est entierement devolue a la preuve du Theoreme 14.En guise de remarque preliminaire, on observera que puisque diam(C4) =

2, tous les quadrangles induits dans un graphe sont des sous-graphes isometriques.Dit autrement, les notions de C4 induit et de C4 isometrique correspondent ;il n’y a pas de cycle induit de longueur 4 et ponte. D’apres le Corollaire 26,si G est 1/2-hyperbolique, alors G2 l’est aussi, ce qui implique G2 est sansC4 d’apres le Theoreme 12. Nous prouvons que de plus :

Claim 9. Supposons le carre G2 sans C4. Alors, C6, C7 et les graphes(a),(b) de la Figure 2 ne sont pas des sous-graphes isometriques de G.

Demonstration. Par l’absurde.D’abord supposons qu’il y ait un cycle isometrique C de longueur 6

dans G. On peut trouver un quadruplet a, b, c, d ∈ V (C) tel que : d(a, b) =d(c, d) = 1 ; d(a, c) = d(b, d) = 2 ; d(a, d) = d(b, c) = 3. Mais alors, un telquadruplet induit un quadrangle dans G2 d’apres le Claim 8, ce qui est unecontradiction.

De meme, supposons qu’il y ait un cycle isometrique C de longueur 7dans G. On peut trouver un quadruplet a, b, c, d ∈ V (C) tel que : d(a, b) = 2et d(c, d) = 1 ; d(a, c) = d(b, d) = 2 ; d(a, d) = d(b, c) = 3. Mais alors, untel quadruplet induit aussi un quadrangle dans G2 d’apres le Claim 8. Unecontradiction.

43

a b

c d

a b

c d

Fig. 10: C4 induits dans G2 depuis un C6 ou un C7 isometrique dans G.

Finalement, pour chacun des graphes (a),(b) de la Figure 2, consideronsle quadruplet de sommets qui sont representes en gras. On peut aisementverifier dans les deux cas qu’un tel quadruplet induit un C4 dans le carre. Parconsequent, aucun des graphes (a),(b) de la Figure 2 n’est un sous-grapheisometrique de G non plus.

Dans la suite, nous ne considererons plus que le grapheG′ de la Definition 13.D’abord, nous devons prouver que G′ doit etre sans C4 pour que G soit 1/2-hyperbolique :

Lemme 30. S’il y a un quadrangle induit dans G′, alors G n’est pas 1/2-hyperbolique.

Demonstration. Soient a, b, c, d ∈ V ′ tels que G′[a, b, c, d] est un C4 induit.Sans perte de generalite on supposera d(a, b) = d(c, d) = 2. Nous distingue-rons plusieurs sous-cas.

Si a, b, c, d ∈ V ×0, alors G[a, b, c, d] est quadrangle induit egalementet donc, G n’est pas 1/2-hyperbolique d’apres le Theoreme 12.

Si a, b, c, d ∈ V × 1, alors G3[a, b, c, d] est aussi un cycle induit delongueur 4, d’ou G3 n’est pas 1/2-hyperbolique d’apres le Theoreme 12. Ceciimplique que G n’est pas 1/2-hyperbolique d’apres le Corollaire 26.

Pour tous les cas restants, nous pretendons qu’il n’y a aucun sommetu ∈ V tel que (u, 0), (u, 1) ⊆ a, b, c, d. Cela vient de ce que NG′((u, 0))∪(u, 0) ⊆ NG′((u, 1)) ∪ (u, 1) ((u, 1) domine (u, 0)). Nous pouvons doncecrire (a, b, c, d) = ((u, i), (v, i′), (x, j), (y, j′)), ou i, i′, j, j′ ∈ 0, 1 et lessommets u, v, x, y sont deux-a-deux distincts dans V .

Supposons i = 0, i′ = j = j′ = 1. Alors il vient que maxdG(u, x) +dG(v, y),dG(u, y) + dG(v, x) ≤ 2 + 3 = 5, tandis que dG(u, v) + dG(x, y) ≥3 + 4 = 7. En d’autres termes, δ(G) ≥ δG(u, v, x, y) ≥ 1.

44

1 1

11

3 3

33

2

32

1 1

1

2

2

2

2

22

1

2

2

3

Fig. 11: Quadrangles possibles dans G′. Les poids sur les aretes represententles distances dans G.

Deuxiemement supposons i = 1, i′ = j = j′ = 0. En particulier, nousavons que x, v, y, v ∈ E et ainsi, dG(x, v) = dG(y, v) = 1, dG(x, y) = 2.Observons que dG(u, x) < 2 ou dG(u, y) < 2 entraınerait que dG(u, v) <3, d’ou a, b ∈ E′, ce qui serait une contradiction. Donc, nous avonsdG(u, x) = dG(u, y) = 2, donc dG(u, v) = 3 et finalement, δ(G) ≥ δG(u, v, x, y) =(5− 3)/2 = 1.

A present supposons i = i′ = 0, j = j′ = 1. Observons que 4 ≤dG(x, y) ≤ dG(u, x)+dG(u, y) ≤ 2+2, d’ou l’on obtient dG(u, x) = dG(u, y) =2. Par symetrie, nous avons aussi dG(v, x) = dG(v, y) = 2. Nous deduisonsde facon similaire dG(x, y) = 4. Alors il s’ensuit que dG(u, x) + dG(v, y) =dG(u, y) + dG(v, x) = 4, tandis que dG(u, v) + dG(x, y) = dG(u, v) + 4 ≥ 6.En d’autres termes, δ(G) ≥ δ(u, v, x, y) ≥ 1.

Finalement, supposons i = j = 0, i′ = j′ = 1. D’apres la Definition 13,dG(u, x)+dG(v, y) = 1+dG(v, y) ≤ 4, dG(u, y)+dG(v, x) ≤ 2+2 = 4, tandisque dG(u, v) + dG(x, y) ≥ 3 + 3 = 6. Donc, on a que δ(G) ≥ δG(u, v, x, y) ≥1.

L’etape finale est de prouver que, lorsque G′ est sans C4, aucun des sous-graphes interdits restants (cf. Theoreme 12) ne peut etre un sous-grapheisometrique de G.

Lemme 31. Supposons G′ sans C4. Alors aucun des graphes C4 et (c),(d),(e),(f)de la Figure 2 n’est un sous-graphe isometrique de G.

45

Demonstration. Nous procedons par l’absurde. D’apres la Definition 13, ilest clair que puisque G′ est sans C4, alors il en va de meme pour G. Pourchacun des quatre autres graphes, nous ne considererons que le quadrupletdes sommets qui sont representes en gras sur la Figure 2.

Considerons le graphe (c) de la Figure 2 comme un sous-graphe isometriquede G. Nous enumerons les quatre sommets du quadruplet dans l’ordre anti-horaire u, y, v, x, en demarrant du sommet u le plus en haut et a gauche surle dessin. Observons que dG(u, x) = 1, dG(u, y) = dG(v, x) = 2, dG(u, v) =dG(x, y) = dG(v, y) = 3. Alors (u, 0), (y, 1), (v, 1), (x, 0) induit un quadrangledans G′. Une contradiction.

Dans les trois autres cas, nous enumerons toujours les quatre sommetsdans l’ordre anti-horaire u, y, v, x, cette fois en partant du sommet le plus agauche.

Considerons le graphe (d) sur la Figure 2 comme un sous-graphe isometriquede G. Observons que toutes les distances sauf dG(x, y) egalent 2, et quedG(x, y) = 4. Par consequent, G′[(u, 0), (y, 1), (v, 0), (x, 1)] est un cycle delongueur 4. A nouveau, ce n’est pas possible.

Deuxiemement, considerons le graphe (e) de la Figure 2 comme unsous-graphe isometrique de G. Observons que dG(u, x) = dG(x, v) = 2,dG(u, v) = 4, et toutes les distances restantes egalent 3. En consequence,G′[(u, 1), (y, 1), (v, 1), (x, 0)] est un C4 induit, ce qui contredit que G′ estsans C4.

Finalement, considerons le graphe (f) de la Figure 2 comme un sous-graphe isometrique de G. Les sommets (u, 1), (y, 1), (v, 1), (x, 1) induisentun cycle sans corde de longueur 4 dans G3, donc dans G′, ce qui est unenouvelle fois une contradiction.

La preuve du Theoreme 14 est ainsi complete, comme le Corollaire 26 etle Lemme 30 montrent que la condition est necessaire, et que le Claim 9 etle Lemme 31 prouvent qu’elle est suffisante d’apres le Theoreme 12.

C Complements a la Section 5

C.1 Graphes Planaires Exterieurs 1/2-hyperboliques

Le but de la Section C.1 est de prouver ce resultat :

Proposition 32. Les graphes planaires exterieurs 1/2-hyperboliques peuventetre reconnus en temps lineaire.

46

Nous verrons dans la Section D que ce resultat reste vrai dans le casplus general ou la largeur d’arborescence est bornee. Comme les graphes pla-naires exterieurs sont K4-minor free, leur largeur d’arborescence est borneepar 2 [10]. La Proposition 32 pourrait donc se deduire directement de laSection D. Neanmoins, une preuve plus naturelle est possible dans ce cas,qui exploite davantage la structure de ces graphes.

Nous commencerons par nous interesser aux cycles isometriques dans ungraphe planaire exterieur G = (V,E). Sans perte de generalite, G est icisuppose biconnexe. En d’autres termes, un plongement planaire exterieurpour G consiste en un cycle non dirige, avec un nombre arbitraire de cordesqui ne s’intersectent pas deux-a-deux. Par ailleurs, on observe que les cordesd’un tel cycle sont des cliques-separatrices de taille 2, ce que nous avons ap-pele une arete-separatrice. Comme un cycle isometrique dans un graphe doitnecessairement etre contenu dans un unique atome (voir la Section 3 pourrappel de la definition), nous retrouvons le resultat precedemment evoquedans la Section 5.1 :

Claim 10. La clique-decomposition d’un graphe planaire exterieur G =(V,E) a pour atomes des cycles non diriges. En outre, ces cycles corres-pondent aux faces d’un plongement planaire exterieur de G, et ils sont exac-tement les cycles isometriques de G.

D’apres le Claim 10, puisqu’on obtient un plongement planaire exterieuren temps lineaire, il vient que la condition necessaire de la Proposition 27, etdonc la Condition 1 qui s’en deduit, peuvent etre verifiees en temps lineairepour les graphes planaires exterieurs.

Nous supposerons la condition de la Proposition 27 satisfaite dans lasuite.

Lemme 33. Soit G = (V,E) un graphe planaire exterieur dont toutes lesboules sont convexes. G est 1/2-hyperbolique si, et seulement si, le graphe(a) sur la Figure 2 n’est pas un sous-graphe induit de G.

Demonstration. D’apres le Theoreme 12, G est 1/2-hyperbolique si, et seule-ment si, aucun des graphes de la Figure 2 n’est un sous-graphe isometriquede G. En outre, les roues contiennent K4 comme mineur, et les graphes(b),(c),(d),(e),(f) sur la Figure 2 contiennent tous une roue comme sous-graphe. Par consequent,G ne contient aucun des sous-graphes (b),(c),(d),(e),(f)de la Figure 2 comme mineur, puisque K4-minor free. En d’autres termes,G est 1/2-hyperbolique si, et seulement si, le graphe (a) de la Figure 2 n’estpas un sous-graphe isometrique de G.

47

u

v

x

Fig. 12: Un mineur K2,3 dans H ′. Les aretes du mineur sont tracees engras. Les sommets colories et de meme couleur doivent etre contractes enun unique sommet.

A present, nous pretendons que le graphe (a) sur la Figure 2 est un sous-graphe isometrique de G si, et seulement si, c’est un sous-graphe induit deG. Nous appellerons ce sous-graphe H dans le reste de la preuve. Clairement,tout sous-graphe isometrique est egalement induit. Reciproquement, suppo-sons H induit mais ponte dans G. En particulier, il doit exister une pairede sommets u, v extremale a distance 3 dans H telle que dG(u, v) = 2. Soitx /∈ V (H) tel que dG(u, v) = dG(u, x)+dG(x, v), et soit H ′ = G[V (H)∪x].Nous sommes en mesure de montrer que H ′ contient K2,3 comme mineur(voir la Figure 12), ce qui est absurde parce que G est K2,3-minor free parhypothese. En consequence, on a montre que toute copie induite de H dansG est isometrique.

Finalement, nous pouvons conclure par une application d’un resultatdans [30] : decider si un graphe planaire est sans H, pour H fixe, peut etreeffectue en temps lineaire.

C.2 Graphes Soleil

En premier lieu, nous ne considererons qu’une classe specifique de graphesplanaires exterieurs, que nous nommerons soleils. Notre but est de prouverque calculer l’hyperbolicite pour un soleil peut etre realise en temps lineaire.Nous en deduirons l’algorithme en temps lineaire pour le cas general dansla section suivante.

L’idee est qu’on a peu de quadruplets a considerer pour l’hyperbolicite,ce qui autorise une methode de type brute-force. Pour le prouver, consideronsd’abord un cycle C non dirige. Nous caracterisons tous les quadruplets pourlesquels δ(C) est atteint.

Lemme 34. Soit C un cycle a n = 4p + r sommets, 0 ≤ r ≤ 3. Il n’existeque O(n) quadruplets a, b, c, d tels que δ(a, b, c, d) = δ(C), et ils peuvent etre

48

a a

a a a

a

a

a a

a

b b b

b

b

b b

b

c c c

c

c

c

c

c

d d d

d

d

d

d

d

b b

c c

d d

p p

pp

p p

p

p p p

p p

p

p p

p

p

p

p p p

p p

p

p+1

p+1 p+1 p+1

p+1 p+1

p+1

p+1

p+1p+1

p+1

p+1

p+2

p+2 p+2

p+3

r=0 r=1

r=2

r=3

Fig. 13: L’ensemble des cas pour la preuve du Lemme 34.

enumeres en temps lineaire.

Demonstration. Rappelons que, d’apres le Lemme 6, on a que δ(C) = p−1/2si r = 1, et δ(C) = p sinon. Nous supposerons dans le reste de la preuvequ’on a fixe une orientation arbitraire pour C. Soit a, b, c, d n’importe quelquadruplet tel que δ(a, b, c, d) = δ(C). Sans perte de generalite, un parcoursanti-horaire de C (defini suivant l’orientation choisie) donne l’ordre a, b, c, dpour ces sommets. Nous pouvons supposer sans perte de generalite (a unerotation pres dans le plan) que d(a, c) ≥ d(b, d), et nous pouvons aussisupposer sans perte de generalite (a une symetrie pres) que d(a, c) = d(a, b)+d(b, c) et d(b, d) = d(a, b) + d(a, d).

Considerons maintenant S1 = d(a, b) + d(c, d), S2 = d(a, c) + d(b, d) etS3 = d(a, d) + d(b, c). On observera que S2 = 2 d(a, b) + d(b, c) + d(a, d) =d(a, b) + (d(c, b) + d(b, a) + d(a, d)) ≥ S1, et que S2 = S3 + 2 d(a, b). D’ou,S2 = maxS1, S2, S3.

En outre, d(a, c) ≥ d(b, d) est a present equivalent a ce que d(b, c) ≥d(a, d). D’apres l’inegalite triangulaire on a que d(a, c) ≤ d(a, d) + d(c, d) etainsi, nous obtenons d(c, d) ≥ d(a, b).

On remarque que mind(a, b),d(b, c),d(c, d), d(a, d) ≥ p − 1/2 d’apresle Lemme 5. Donc, mind(a, b), d(b, c), d(c, d),d(a, d) ≥ p, puisque toutesles distances sont des entiers positifs. De meme on rappelle que d(a, b) +d(b, c) + d(c, d) + d(a, d) = n par hypothese. En particulier, quand r = 0, la

49

seule solution est que d(a, b) = d(b, c) = d(c, d) = d(a, d) = p.Quand r = 1, la seule solution est maxd(a, b), d(b, c),d(c, d),d(a, d) =

maxd(b, c),d(c, d) = p + 1, tandis que les trois autres distances dansd(a, b),d(b, c), d(c, d),d(a, d) egalent p. Par ailleurs, puisque d(a, c) = d(a, b)+d(b, c), il vient que d(c, d) = maxd(b, c),d(c, d) = p+ 1.

Quand r = 2, deux cas sont a prendre en compte : soit les deux plusgrandes distances egalent p + 1 et les deux restantes sont egales a p, soitmaxd(b, c), d(c, d) = p+2 et les trois autres distances dans d(a, b), d(b, c),d(c, d),d(a, d)valent p. Dans le premier cas, soit les deux plus larges distances sont d(b, c)et d(c, d), ou d(b, c) et d(a, d), ou d(a, b) et d(c, d) ; pour tous ces sous-cas,nous avons bien δ(a, b, c, d) = p. Dans le second cas, un raisonnement si-milaire a celui deja donne pour r = 1 montre que δ(a, b, c, d) = p − 1. Enconsequence de quoi, seul le premier cas mene a la valeur δ(C).

Finalement, quand r = 3, trois cas sont a considerer.– D’abord supposons d(b, c) = d(c, d) = maxd(a, b),d(a, d) = p + 1

et mind(a, b), d(a, d) = p. Puisque d(a, c) = d(a, b) + d(b, c), il vientque mind(a, b),d(a, d) = d(a, b). On a alors que δ(a, b, c, d) = (S1 −S3)/2 = ((4p+ 2)− (2p+ 2))/2 = p.

– Deuxiemement, supposons maxd(b, c), d(c, d) = p + 2, la deuxiemeplus grande distance dans d(a, b),d(b, c),d(c, d), d(a, d) vaut p + 1,et les deux distances restantes dans cet ensemble egalent p. Si d(b, c) =maxd(b, c),d(c, d) = p+2, alors on a que d(a, b)+d(b, c) ≥ 2p+2 etd(a, d) + d(c, d) ≤ 2p+ 1. C’est absurde, car d(a, c) = d(a, b) + d(b, c).Donc, on a que d(c, d) = p + 2 et ainsi, maxd(a, b),d(b, c) = p + 1,tandis que mind(a, b), d(b, c) = d(a, d) = p. A noter qu’on en deduitegalement S1 ≥ 2p + 2 tandis que S3 ≤ 2p + 1, d’ou S1 ≥ S3. Parconsequent, δ(a, b, c, d) = (S2−S1)/2 = (2 d(a, b)+d(b, c)+p−d(a, b)−p−2)/2 = (d(a, b)+d(b, c)−2)/2 = (2p−1)/2 = p−1/2. Ceci impliqueclairement que δ(C) = p ne peut pas etre atteint dans ce cas.

– Finalement, supposons maxd(b, c), d(c, d) = p+ 3 et les trois autresdistances dans d(a, b), d(b, c), d(c, d),d(a, d) egales a p. Puisque d(a, c) =d(a, b) + d(b, c), il vient a nouveau que maxd(b, c),d(c, d) = d(c, d).Ainsi, on obtient δ(a, b, c, d) = (S2−S1)/2 = (4p−(2p+3))/2 = p−3/2,ce qui est different de δ(C) = p.

Il est direct que, des que les quatre distances d(a, b), d(b, c),d(c, d), d(a, d)sont connues et fixees, il n’y a que O(n) quadruplets dans C qui satisfontles contraintes requises sur leurs distances deux-a-deux. De plus, tous cesquadruplets sont enumerables par un simple parcours anti-horaire du graphe

50

Fig. 14: Un soleil.

(defini selon son orientation arbitraire). En consequence, l’enumeration peutetre realisee en temps lineaire.

Une remarque utile est que, d’apres le Lemme 6, calculer l’hyperbolicitepour un cycle est faisable en temps lineaire sans recourir a l’enumeration duLemme 34 : en effet, il suffit juste dans ce cas de calculer l’ordre du graphe,puis de le diviser par 4, et nous pouvons conclure. Considerons maintenantune legere extension de la classe des cycles, dont font partie les substitutsdes cycles en tant qu’atomes que nous avions mentionne en Section 5 :

Definition 35. Soit G = (V,E) un graphe connexe. G est un soleil s’ilexiste une bipartition V1, V2 de V telle que :

– G[V1] est un cycle C ;– le voisinage de chaque sommet dans V2 induit une arete dans C ;– une arete de C est induite par le voisinage d’au plus un sommet.

Par ailleurs, C est appele le cycle dominant de G.

Un exemple de soleil est presente sur la Figure 14. Clairement, tout so-leil est planaire exterieur. De plus, les atomes d’un soleil (Section 3) sontune union de triangles, plus son cycle dominant. Cela signifie que nous pou-vons appliquer le Theoreme 10 directement. Nous montrerons neanmoinsque dans ce cas restreint, le resultat du Theoreme 10 sur l’erreur additivesur l’hyperbolicite du graphe peut etre ameliore :

Proposition 36. Soit G = (V,E) un soleil, et soit C son cycle dominant.La double inegalite δ(C) ≤ δ(G) ≤ δ(C) + 1/2 est satisfaite. De plus, δ(G)est calculable en temps lineaire.

Demonstration. Soit V1, V2 une bipartition de V telle que G[V1] = C, donton peut facilement observer qu’elle est unique. Remarquons, comme dit ci-dessus, que les atomes de G sont exactement C plus tous les G[v ∪NG(v)]avec v ∈ V2 ; par ailleurs, pour tous les v ∈ V2, G[v ∪NG(v)] est un triangle.En consequence, on obtient δ(C) ≤ δ(G) ≤ δ(C)+1 d’apres le Theoreme 10.

Nous raisonnons a present par l’absurde pour raffiner la borne superieure.Nous pretendons que δ(G) = δ(C) + 1 entraınerait l’existence d’un a ∈ V1

51

b1

b2

b3x3

y3

x2y2

x1

y1a

Fig. 15: Un quadruplet du type (a|b1, b2, b3).

et d’un triplet b1, b2, b3 ∈ V2 tel que δ(a, b1, b2, b3) = δ(C) + 1. D’abord,par une application directe du Lemme 5 tout quadruplet a, b, c, d tel queδ(a, b, c, d) = δ(C) + 1 doit satisfaire |a, b, c, d ∩ V2| ≥ 3 ; notre conditionest donc necessaire. Pour la partie suffisante, nous fixons au prealable uneorientation pour C, que nous conserverons pour la suite de la preuve. Soientbi, bj ∈ V2 ; on peut toujours ecrire NG(bk) = xk, yk pour tout k ∈ i, j,ou xkyk est un arc dans C (suivant l’orientation choisie). En tirant partie decette convention, il peut etre facilement verifie que d(bi, bj) = d(xi, xj)+1 =d(yi, yj) + 1. Par consequent, pour tout quadruplet b1, b2, b3, b4 ∈ V2, il s’endeduit l’existence d’un quadruplet x1, x2, x3, x4 ∈ V1 tel que δ(b1, b2, b3, b4) =δ(x1, x2, x3, x4) ≤ δ(C).

Finalement, soit a ∈ V1 et soient b1, b2, b3 ∈ V2. Nous conservons les no-tations precedentes : une orientation arbitraire pour C est fixee, et pour touti, nous avons NG(bi) = xi, yi, avec xiyi un arc dans C (selon l’orientationchoisie). Soient S1, S2, S3 les trois sommes partie prenante dans le calcul deδ(a, b1, b2, b3) ; soient S′1, S

′2, S′3 les trois memes sommes partie prenante dans

le calcul de δ(a, x1, x2, x3). Puisque pour tout i on a que d(a, xi) ≤ d(a, bi) ≤d(a, xi) + 1, il vient que S′i + 1 ≤ Si ≤ S′i + 2. En consequence, il s’ensuitque δ(a, b1, b2, b3) ≤ δ(a, x1, x2, x3) + 1/2 ≤ δ(C) + 1/2. La borne superieureest donc prouvee par contradiction.

Notre interet d’avoir reduit cette borne de 1/2 n’est pas seulement theorique.En effet, considerons un quadruplet a, b, c, d tel que δ(a, b, c, d) = δ(G).Chacun des sommets du quadruplet peut etre remplace par un sommet ducycle C : soit lui-meme ou un de ses deux voisins dans C. On obtient unnouveau quadruplet a′, b′, c′, d′ ∈ V1. Par ailleurs, soit δ(G) = δ(C), soitδ(G) = δ(C) + 1/2 et alors : δ(C) + 1/2 = δ(a, b, c, d) ≤ δ(a′, b′, c′, d′) + 1/2d’apres le paragraphe precedent, ce qui entraıne δ(a′, b′, c′, d′) = δ(C). End’autres termes, nous pouvons restreindre notre etude aux quadruplets maxi-maux de C (ceux qui atteignent la valeur δ(C)), et a leur voisinage dans V2.

Or, on observe que pour tout sommet du cycle v ∈ V1, on a que |NG(v)∩V2| ≤ 2. D’apres le Lemme 34, tous les quadruplets a, b, c, d ∈ V1 tels que

52

δ(a, b, c, d) = δ(C) peuvent etre enumeres en temps lineaire. Donc, pour tousces quadruplets-la, nous pouvons verifier s’il est possible d’en augmenter lo-calement la valeur de l’hyperbolicite de 1/2, par la prise en compte de leurnombre (borne par 8) de voisins dans V2. On notera, pour etre complet,que le calcul des distances peut se faire ici en temps constant, car les dis-tances deux-a-deux pour les sommets dans a, b, c, d sont connues et fixees.Il s’en deduit finalement un algorithme en temps lineaire pour le calcul del’hyperbolicite.

C.3 Preuves pour la Section 5.1

Nous rassemblons a present les preuves des Sections C.1 et C.2 pourdonner la preuve du Theoreme 16, dont l’intuition et l’algorithme associeont deja ete donnes dans la Section 5.1.

La preuve que les graphes planaires exterieurs d’hyperbolicite 1/2 peuventetre reconnus en temps lineaire est l’objet de la Proposition 32. Nous pou-vons donc effectivement supposer G biconnexe et δ(G) ≥ 1. Le Claim 10 for-malise notre observation precedente selon laquelle la clique-decompositiond’un graphe planaire exterieur peut se calculer en temps lineaire. Nous ensommes donc ramenes a la preuve que les substituts des atomes peuvent etreconstruits en temps lineaire.

Rappelons que d’apres le Lemme 9, l’hypothese δ(G) ≥ 1 entraıne quenous pouvons ignorer sans risque les quadruplets de type (a1, a2|b1, b2) lorsde la decomposition du graphe selon ses aretes-separatrices. De meme quedans la Section A, nous nous interessons a present au cas ou δ(G) > 1.

Claim 11. Soit δ(a, b, c, d) ≥ 32 . Il existe un cycle isometrique C dans G

tel que, pour tout sommet u ∈ a, b, c, d, soit u ∈ V (C), soit il existe unearete-separatrice xu, yu ∈ E(C) qui separe u de a, b, c, d \ u.

Demonstration. D’apres le Corollaire 23, il existe un atome A tel que pourtout sommet u ∈ a, b, c, d, soit u ∈ A soit il existe une clique-separatriceXu ⊆ A telle que Xu separe u de a, b, c, d \ u. Par ailleurs, d’apres leClaim 10, un tel atome A est un cycle isometrique C de G. Il s’ensuit que lescliques maximum dans C sont les aretes dans E(C). En consequence, chaqueclique-separatrice qui est contenue dans C est une arete-separatrice.

Nous considerons a present un cycle isometrique C de G qui satisfait lacondition du Claim 11 pour le quadruplet a, b, c, d. D’apres le Lemme 17 (etd’apres la reduction du Claim 1), pour tout sommet u ∈ a, b, c, d, nouspouvons supposer sans perte de generalite (a une substitution de u pres par

53

un sommet de C et qui ne change pas la valeur pour l’hyperbolicite) que s’ilexiste une arete-separatrice xu, yu ∈ E(C) qui separe u de a, b, c, d\u,alors on a : d(u, xu) = d(u, yu) = 1. En d’autres termes :

Claim 12. Il existe un soleil GS tel que δ(G) = δ(GS). En outre, le cycledominant de GS est isomorphe a un cycle isometrique de G.

En fait, il est direct, d’apres le Corollaire 36, que le soleil GS du Claim 12peut etre suppose avoir son cycle dominant CS isomorphe a un cycle isometriquedeG d’hyperbolicite maximum. En pratique, le nombre d’atomes a considererpeut ainsi s’en trouver reduit. Reste a prouver que l’ensemble des choix pos-sibles pour GS peut s’enumerer en temps lineaire. Dans la Section 5.1, nousavons introduit dans ce but l’arbre dual (weak dual). Nous en rappelonsci-dessous la definition, dans une version plus formelle :

Definition 37. ( [2]) Soit G = (V,E) un graphe planaire exterieur bicon-nexe. Considerons un plongement planaire exterieur pour G, qui est contenuet delimite par un cercle C. Nous appelons faces interieures toutes les facesdu plongement qui sont contenues dans le disque delimite par C. Alors,l’arbre dual de G est un arbre TG dont les sommets sont les faces interieuresdu plongement ; deux faces interieures sont adjacentes dans TG si, et seule-ment si, elles ont en commun une arete-separatrice dans le plongement pla-naire exterieur de G.

Nous rappelons que la Figure 4 illustre la construction presentee dansla Definition 37. A noter egalement que, puisque un plongement planaireexterieur peut etre obtenu en temps lineaire, alors il en est de meme pourl’arbre dual de G.

Ce qui suit correspond a divers pre-traitements pour l’algorithme de laSection 5.1, tous realisables en temps lineaire, et dont le resultat peut aussietre stocke pour utilisation ulterieure en n’utilisant qu’un espace de taillelineaire.

– D’une part, les aretes dans TG doivent toutes etre etiquetees, de faconunique, par les aretes-separatrices de G.

– Nous supposerons, d’autre part, que chaque sommet de l’arbre dualfournit un pointeur vers le cycle isometrique du graphe qu’il represente.

– On exige de pouvoir connaıtre la parite de la longueur d’un cycleisometrique en temps constant.

– Enfin, dans le cas ou l’atome considere est un cycle de longueur paire,on impose de pouvoir consulter en temps constant l’arete diametralementopposee dans le cycle a n’importe quelle arete e de l’atome.

54

Toutes ces operations peuvent etre realisees en temps et en espace lineaires,par un simple parcours de chaque face du plongement planaire exterieur. Cefaisant, nous avons completement demontre la linearite de notre algorithme.

Notre ultime etape sera de prouver la construction intuitive des substi-tuts, que nous avons deja mentionnee dans la Section 5.1. Nous la formalisonspar le biais du Lemme 38 :

Lemme 38. Soient C1, C2 deux cycles isometriques de G, qui ont en com-mun l’arete-separatrice e = x, y. Soient A,B les deux composantes connexesde G[V \ e] telles que C1 ⊆ A∪ e et C2 ⊆ B ∪ e. S’il existe un quadruplet detype (a|b1, b2, b3) tel que δ(a, b1, b2, b3) > δ(B), alors :

– ou bien la longueur de C1 est impaire ;– ou bien l’arete e′ = x′, y′ qui est diametralement opposee a e dansC1 separe a de C1.De plus, dans ce dernier cas, soit C0 l’unique cycle isometrique qui par-tage l’arete e′ avec C1, et soient A′, B′ les deux composantes connexesde G[V \ e′] telles que C0 ⊆ A′ ∪ e′ et C1 ⊆ B′ ∪ e′. Alors a peutegalement etre complete en un quadruplet du type (a|b′1, b′2, b′3) tel queδ(a, b′1, b

′2, b′3) > δ(B′).

Demonstration. Puisque l’arete e est une (a|b1, b2, b3)-clique-separatrice, etque δ(a, b1, b2, b3) > maxδ(x, b1, b2, b3), δ(y, b1, b2, b3) par hypothese, il s’en-suit que d(a, x) = d(a, y). Deux cas sont a considerer.

– Si a ∈ C1, alors a est un sommet diametralement oppose a e dans C1,ce qui implique que la longueur de C1 est impaire.

– Supposons que a /∈ C1. Alors il existe une arete-separatrice e′ =x′, y′ ∈ E(C1) qui separe a de C1 (et de B).Sans perte de generalite, d(a, x′) ≤ d(a, y′). Comme d(a, x) = d(a, y)donc : soit e′ est diametralement opposee a e dans C1, soit d(a, x′) <d(a, y′), ce dont on deduit δ(a, b1, b2, b3) = δ(x′, b1, b2, b3) (tous les pluscourts chemins entre a et e peuvent passer par x′), ce qui nous rameneau cas precedent ou a ∈ C1.Supposons donc e′ diametralement opposee a e dans C1. En particulier,la composante B′∪e′ de l’enonce du Lemme contient C1 et B. Donc, s’iln’existe pas de quadruplet du type (a|b′1, b′2, b′3) tel que δ(a, b′1, b

′2, b′3) >

δ(B′), alors en particulier pour b′1, b′2, b′3 = b1, b2, b3 on en deduitl’existence d’un sommet a′ ∈ B′ \ (B ∪ e) tel que δ(a′, b1, b2, b3) =δ(a, b1, b2, b3). Si a′ /∈ V1, alors a′ est separe de C1 et de B par unearete-separatrice e” qui n’est pas diametralement opposee a e dansC1, et donc on peut conclure. Sinon, a′ ∈ V1, et on s’en ramene denouveau au premier cas.

55

Le Lemme 38 termine la preuve formelle du Theoreme 16.

D Hyperbolicite et Largeur Arborescente

Dans cette breve Section, nous passerons en revue plusieurs parametresde la theorie des graphes, la plupart pouvant etre vus comme une mesurede la proximite du graphe avec un arbre selon certaines proprietes. Nousnous interesserons aux relations entre ces parametres et l’hyperbolicite dugraphe.

Le resultat principal de la Section D sera un algorithme en temps lineairepour reconnaıtre les graphes 1/2-hyperboliques dont la largeur d’arbores-cence est bornee par une constante.

Pour commencer, une decomposition arborescente d’un graphe G = (V,E)est la donnee d’un arbre T = (V ′, E′) et d’une fonction W : V ′ → 2V . Onimpose que cette decomposition satisfait deux contraintes :

– pour toute arete x, y ∈ E, il doit exister un sommet t ∈ V ′ tel quex, y ⊆Wt ;

– pour tout sommet u ∈ V on a que T [Xu] est un sous-arbre de T , avecXu = t ∈ V ′ : u ∈Wt.

En particulier, la decomposition arborescente est dite connexe si pour chaquesommet t ∈ V ′ de l’arbre, on a que G[Wt] est un sous-graphe connexe de G.La largeur d’une decomposition est definie comme : maxt∈V ′ |Wt| − 1.La longueur d’une decomposition est definie comme : maxt∈V ′ maxu,v∈Wt d(u, v).

Trois parametres importants (pour notre etude) peuvent se definir a l’aided’une telle decomposition.

– la largeur d’arborescence de G (ou treewidth), notee tw(G), est la pluspetite largeur possible pour une decomposition arborescente de G ;

– la longueur d’arborescence de G (ou tree-length), notee tl(G), est laplus petite longueur possible pour une decomposition arborescente deG ;

– la largeur d’arborescence connexe de G (ou connected treewidth), noteectw(G), est la plus petite largeur possible pour une decompositionarborescente connexe de G.

Nous ajouterons a cette liste un quatrieme parametre :

56

– le plus long cycle isometrique dans G, que nous noterons dans la suitelic(G).

Il est connu, de longue date, que les parametres tw(G) et δ(G) sont in-comparables. Dans un sens, cela vient de ce qu’un graphe complet d’ordre na pour largeur d’arborescence n− 1, bien qu’il soit d’hyperbolicite 0. Dansl’autre sens, on peut le voir avec les cycles d’ordre n, d’hyperbolicite arbi-trairement grande (Lemme 6), mais de largeur d’arborescence 2.

En revanche, tl(G) et δ(G) sont comparables. Plus precisement, la lon-gueur d’arborescence d’un graphe est une O(log n)-approximation de sonhyperbolicite : δ(G) ≤ tl(G) ≤ (12 + 8 log n)δ(G) + 17 [19].

Les relations entre δ(G) et ctw(G) n’ont pas ete etudiees a notre connais-sance. Cependant, il est prouve dans [54] que :ctw(G) ≤ tw(G) +

(tw(G)+1

2

)(lic(G)tw(G)− 1).

Enfin, il n’est pas difficile de montrer lic(G) ≤ 4δ(G) + 3. Cependant, lafamille des graphes pontes (definie comme les graphes pour lesquels lic(G) ≤3) admet des graphes d’hyperbolicite arbitrairement grande, ce qui prouvemalheureusement qu’une borne superieure pour δ(G) n’est pas deductiblede ce seul parametre [46].

Nous combinons ces resultats pour donner ce qui est, a notre connais-sance, la premiere relation connue entre largeur d’arborescence et hyperbo-licite :

Proposition 39. Soit G un graphe connexe.δ(G) ≤ tl(G) ≤ ctw(G) ≤ tw(G) +

(tw(G)+1

2

)(lic(G)tw(G)− 1)

≤ tw(G) +(tw(G)+1

2

)[(4δ(G) + 3)tw(G)− 1] ≤ O(tw(G)3δ(G)).

Demonstration. L’unique observation necessaire est que, dans une decompositionarborescente connexe, la longueur d’arborescence est toujours majoree par lalargeur d’arborescence. D’ou : tl(G) ≤ ctw(G). Le reste se deduit immediatementdes relations presentees ci-dessus.

Une premiere consequence est qu’un algorithme d’approximation generiquepour l’hyperbolicite est definissable pour les graphes dont la largeur d’arbo-rescence est bornee par une constante :

Corollaire 40. Il existe un algorithme en temps lineaire qui retourne uneO(tw(G)3)-approximation pour l’hyperbolicite.

Demonstration. D’apres [27], il existe un algorithme en temps lineaire pour

57

une 3-approximation de tl(G) 1. D’apres la Proposition 39, cette valeur estaussi une O(tw(G)3)-approximation pour l’hyperbolicite.

En particulier, le Corollaire 40 est interessant pour les graphes G telsque tw(G) = O((log n)

13 ) (le parametre tl(G) etant connu pour etre une

O(log n)-approximation de l’hyperbolicite).Cet algorithme d’approximation generique est ce dont nous avions be-

soin pour aboutir a une reconnaissance en temps lineaire des graphes 1/2-hyperboliques, dans le cas des graphes de largeur d’arborescence bornee.

Proposition 41. Decider si un graphe connexe G est 1/2-hyperbolique peutetre realise en temps O(f(tw(G))n+m).

Demonstration. Nous calculons d’abord tw(G) en tempsO(f1(tw(G))n) [11].Puis nous reprenons l’algorithme de la Section 4.1 (voir aussi la Section B.3).

Montrons comment verifier la Condition 1 en temps O(f2(tw(G))n+m).On commence par calculer une O(tw(G)3)-approximation de l’hyperboliciteen temps O(n + m) (Corollaire 40). Clairement, si la valeur retournee esttrop grande, ce qu’on peut verifier puisque tw(G) nous est connu, alors legraphe G n’est pas 1/2-hyperbolique. Dans le cas contraire, on a d’apres leLemme 6 que tous les cycles de G d’une taille Ω(tw(G)3) sont pontes. Pourverifier la Condition 1, il reste encore a prouver que tous les cycles dans Gde longueur au moins 8 et au plus O(tw(G)3) sont pontes.

Nous nous proposons, dans ce but, de definir un predicat Ej , j = O(tw(G)3),pour la relation ”x et y sont adjacents dans Gj” (voir la Section B.1 pourun rappel sur les puissances de graphe). Un tel predicat est definissablerecursivement, comme formule logique MSO2, par la relation E1(x, y) :=E(x, y), et Ej(x, y) := Ej−1(x, y) ∨ (∃zE(x, z) ∧ Ej−1(z, y)). Aide de cepredicat, nous pouvons definir une formule MSO2 qui verifie si la puissanceGj est sans C4 : Rj := ∃a∃b∃c∃dEj(a, c) ∧ Ej(b, c) ∧ Ej(b, d) ∧ Ej(a, d) ∧¬Ej(a, b) ∧ ¬Ej(c, d).

Si G est d’hyperbolicite 1/2, alors Gj est 1/2-hyperbolique d’apres leCorollaire 26 pour n’importe quelle valeur de j et donc, la formule Rj doit

1Pour etre exact, la methode dans [27] retourne une decomposition arborescente de Gde longueur au plus 3tl(G)+1. Mais les auteurs n’indiquent pas clairement si leur methoderetourne la longueur, ou s’il est necessaire de la calculer a partir de leur decomposition.Dans le cas ou il faudrait faire le calcul, soit α(n) la fonction inverse d’Ackermann. Nouspouvons construire un oracle en tempsO(f(tw(G))n), qui calcule n’importe quelle distancedans le graphe en temps O(tw(G)4α(n)) [18]. Une analyse plus fine de la decompositiondans [27] nous montre qu’a l’aide de cet oracle, une 2-approximation pour la longueur dela decomposition peut se deduire en temps quasi-lineaire O(tw(G)4nα(n)).

58

etre fausse d’apres le Theoreme 12.Par ailleurs, il n’est pas difficile de voir que, si C est un cycle isometriqued’ordre 4p + ε dans G, p ≥ 2 et ε ∈ 0, 1, 2, 3, alors il y a un C4 induitdans la puissance G2p−1 ; pour s’en convaincre, il suffit de prendre quatresommets dans C de distances deux-a-deux p, p+b ε2c, p+(d ε2e−min1, d ε2e)et p+ min1, d ε2e.Par consequent, nous proposons comme approche de tester la formule

∧O(tw(G)3)j=8 ¬R2j−1.

Si elle est fausse, alors G n’est pas 1/2-hyperbolique. Sinon, la Condition 1est satisfaite.D’apres le Theoreme de Courcelle, le test d’une formule MSO2 est realisableen temps O(f2(tw(G))n) [23].

Il reste finalement a verifier la condition du Theoreme 14. En d’autrestermes, nous en sommes ramenes a nous assurer que les graphes G2 et G′

sont sans C4, ou G′ designe le graphe de la Definition 13. Nous pouvonsproceder pour G2 comme nous avons procede pour les autres puissances degraphes Gj ci-dessus.

Le graphe G′ necessite plusieurs predicats pour la relation d’adjacencequi lui est associee. Dans un premier temps, on remarque que le predicatE(x, y) donne directement un predicat pour la relation ”(x, 0) et (y, 0) sontadjacents dans G′”. Le predicat E3(x, y), qu’on a defini plus haut, donneun predicat pour la relation ”(x, 1) et (y, 1) sont adjacents dans G′”. Fina-lement, on definit le predicat E′2(x, y) := (x = y)∨E2(x, y) pour la relation”(x, 0) et (y, 1) sont adjacents dans G′” (resp. ”(x, 1) et (y, 0) sont adjacentsdans G′”, par symetrie de notre construction).

Notre but est de construire une formule MSO2 notee Ri,i′,j,j′ , aveci, i′, j, j′ ∈ 0, 1, qui determine s’il existe un C4 induit par un quadruplet(a, i), (b, i′), (c, j), (d, j′) du graphe G′.

– Si i = i′ = j = j′ = 0, alors R0,0,0,0(a, b, c, d) := E(a, c) ∧ E(c, b) ∧E(b, d) ∧ E(d, a) ∧ ¬E(a, b) ∧ ¬E(c, d).

– Si i = i′ = j = j′ = 1, alors R1,1,1,1(a, b, c, d) := E3(a, c) ∧ E3(c, b) ∧E3(b, d) ∧ E3(d, a) ∧ ¬E3(a, b) ∧ ¬E3(c, d) ≡ R3(a, b, c, d).

– Si i = 0, i′ = j = j′ = 1, alors R0,1,1,1(a, b, c, d) := E′2(a, c)∧E3(c, b)∧E3(b, d) ∧ E′2(d, a) ∧ ¬E′2(a, b) ∧ ¬E3(c, d).

– Si i = 1, i′ = j = j′ = 0, alors R1,0,0,0(a, b, c, d) := E′2(a, c) ∧ E(c, b) ∧E(b, d) ∧ E′2(d, a) ∧ ¬E′2(a, b) ∧ ¬E(c, d).

– Si i = i′ = 0, j = j′ = 1, alors R0,0,1,1(a, b, c, d) := E′2(a, c)∧E′2(c, b)∧E′2(b, d) ∧ E′2(d, a) ∧ ¬E(a, b) ∧ ¬E3(c, d).

– Enfin, si i = j = 0, i′ = j′ = 1, alors R0,1,0,1(a, b, c, d) := E(a, c) ∧

59

E′2(c, b) ∧ E3(b, d) ∧ E′2(d, a) ∧ ¬E′2(a, b) ∧ ¬E′2(c, d).Tester si G′ est sans C4 se reduit finalement a tester les six formules MSO2

ci-dessus, ce qui est faisable en temps O(f2(tw(G))n) d’apres le Theoremede Courcelle.

E Grilles Hexagonales et Contractions d’Aretes

Les grilles ”hexagonales” ont ete brievement introduites dans [46], commeun exemple contre-intuitif de graphes qui, bien que pontes, peuvent avoirune valeur pour l’hyperbolicite qui est arbitrairement grande. Pour rap-pel, un graphe est ponte si tous ses cyles de taille au moins 4 sont pontes.Les grilles hexagonales ont egalement une largeur d’arborescence arbitraire-ment grande, puisque contenant des grilles de larges dimensions comme sous-graphes [59]. Ce resultat aurait pu se deduire de ceux de la Section D : desgraphes pontes d’hyperbolicite aussi grande que l’on veut doivent forcementavoir une largeur d’arborescence non bornee.

Definir les grilles hexagonales formellement s’apparente plus a une ga-geure qu’autre chose. Pour tacher d’y parvenir, on notera d’abord qu’unquadrangle, ou C4, peut etre minimalement triangule d’exactement deuxfacons differentes, et qui correspondent dans les deux cas a l’ajout d’unearete entre deux sommets a distance 2 dans le graphe. En particulier, quandon considere le carre comme carte planaire canonique du C4, cela revient aajouter au choix une des deux diagonales possibles. Ces deux triangulationsdu cycle de taille 4 correspondent en fait aux deux motifs de base de lagrille hexagonale. Partant d’une grille ”classique” (ses C4 ne sont donc pasencore triangules), on fixe un plongement dans le plan de celle-ci, de sortequ’ensuite :

– les C4 sur une meme ligne sont minimalement triangules de maniereidentique (i.e. la meme diagonale est ajoutee pour chacun d’entre eux) ;

– deux C4 consecutifs sur une meme colonne sont minimalement trian-gules de facon differente (i.e. une diagonale differente a ete ajoutee).

Cette definition, qui n’est pas completement formelle, peut mieux se com-prendre grace a la Figure 16. A un isomorphisme pres, il y a (au plus) deuxgrilles hexagonales differentes qui peuvent etre construites selon la memegrille classique (selon quelle dimension est choisie pour les lignes). En outre,il est a noter que par cette construction, nous avons defini un carte planaire”canonique” pour les grilles hexagonales. Nous nous refererons toujours im-plicitement a cette derniere dans la suite.

Dans cette annexe, nous nous proposons de completement caracteriser

60

Fig. 16: Un exemple de Grille Hexagonale.

l’hyperbolicite des grilles hexagonales (Proposition 42), ce qui n’avait pas etefait dans [46], et qui viendra ainsi completer les familles simples de graphessur lesquelles on peut s’appuyer pour borner inferieurement l’hyperbolicite(voir les Lemmes 6 et 7). Connaıtre l’hyperbolicite de ces graphes a aussi desapplications pour l’etude preliminaire de l’heuristique proposee dans [45], etque nous exposerons dans la derniere partie de cette Section.

Dans la suite, nous designerons par n+1 le nombre de colonnes, et par m+1 le nombre de lignes. Ces deux parametres sont suffisants pour caracteriserla grille hexagonale etudiee de facon unique. Nous designerons celle-ci parHex(n,m).

Distances dans une Grille Hexagonale

Connaıtre la valeur de l’hyperbolicite requiert certaines connaissancessur les distances dans le graphe. Dans cette Section, afin de faciliter le rai-

61

1

2

3

Fig. 17: Trois regles de substitution.

sonnement, nous supposerons que les colonnes ont ete numerotees de lagauche vers la droite, et les lignes du haut vers le bas. Dans les deux cas, onpart de 0, d’ou la numerotation 0, . . . n pour les colonnes et 0 . . .m pour leslignes. Il s’ensuit evidemment un etiquetage unique de chaque sommet u parson numero de colonne xu et son numero de ligne yu. Par ailleurs, les grilleshexagonales n’etant somme toute qu’une extension des grilles classiques, ilest previsible qu’il existe des relations entre la distance d(u, v) et les coor-donnees xu, xv, yu, yv, et cela pour n’importe quels sommets u, v. Notre butest a present de les exprimer, dans le but avoue d’obtenir une caracterisationpartielle des paires localement eloignees dans le graphe (voir le Lemme 4,ainsi que le paragraphe qui le precede, pour rappel).

D’abord on observera qu’en raison des nombreuses symetries du graphe(ou plutot de sa carte planaire), on pourra toujours supposer sans perte degeneralite que xv ≥ xu et yv ≥ yu (a quelques transformations isometriquespres de la carte planaire). Nous noterons dans la suite ∆x(u, v) = |xu−xv| =xv − xu, et ∆y(u, v) = |yu − yv| = yv − yu.

A present, montrons comment restreindre les plus courts chemins a considererdans notre etude. En premier lieu, il est evident qu’on peut toujours s’eviterd’augmenter ∆x ou ∆y. Nous avons ensuite defini trois regles de substitutionqui sont illustrees par la Figure 17. Ce faisant, nous avons demontre qu’ilexistait toujours un plus court chemin entre u et v tel que :

– tous les mouvements horizontaux, s’il y en a, sont regroupes en un seulchemin horizontal, dont v est une extremite ;

– il y a un unique mouvement vertical d’effectue entre deux mouvementsdiagonaux consecutifs (de la gauche vers la droite et du haut vers le

62

...

1

2

k

u

v

xv - xu = kyv - yu = 2k-1

...

1

k

u

v

xv - xu = kyv - yu = 2k

Fig. 18: Les deux cas a considerer.

bas) ;– Si un chemin vertical a pour une de ses extremites le sommet u, alors

ce chemin se limite a un seul mouvement vertical.Ici, les mouvements dont il est question sont des aretes, dont on considere

qu’elles sont verticales, horizontales ou diagonales, selon l’orientation de lacarte planaire canonique de la grille hexagonale.

Par ailleurs, il est clair que, par definition d’un plus court chemin, lenombre de mouvement diagonaux doit toujours y etre maximise (sans quoinous pourrions en diminuer la longueur !). Les conditions ci-dessus amenentalors naturellement a la definition d’un unique plus court chemin entre u etv, que nous appellerons leur plus court chemin canonique par la suite. Soitk le nombre de mouvements diagonaux sur le plus court chemin canoniqueentre u et v. Alors, en utilisant les deux cas de la Figure 18, on peut aisementverifier que d(u, v) = ∆x(u, v) + ∆y(u, v)− k.

Dans le cas de la Figure E (gauche), la maximisation du nombre de mou-vements diagonaux nous donne k = min∆x(u, v), b∆y(u,v)+1

2 c. Dans le casde la Figure E (droite), on obtient en revanche k = min∆x(u, v), b∆y(u,v)

2 c.Il est a noter que, dans les deux cas, la valeur obtenue pour k est la memepourvu que ∆y(u, v) soit pair. Cette observation n’apparaıt pas tellementsurprenante, une fois considerees plus en details les alternances de triangu-lations de ligne en ligne (e.g. comprendre que la seule configuration attei-gnable dans ce cas-la est la configuration (a) de la Figure 19, a une symetriepres). En revanche, la valeur de k peut differer quand ∆y(u, v) est impair.Aux symetries pres de la grille hexagonale, nous pouvons donc finalementcaracteriser les distances possibles entre n’importe quels sommets u, v dugraphe.

Claim 13. Il existe au plus trois possibilites differentes pour la valeur d(u, v) :

63

u

v

u

v

configuration (a) configuration (b)

Fig. 19: Les deux configurations possibles.

– d(u, v) = ∆y(u, v) ; en ce cas, le plus court chemin canonique contient∆x(u, v) mouvements diagonaux (type I) ;

– d(u, v) = ∆x(u, v)+b∆y(u,v)2 c ; en ce cas, nous sommes dans la configu-

ration (a) de la Figure 19, et le plus court chemin canonique contientb∆y(u,v)+1

2 c = d∆y(u,v)2 e mouvements diagonaux (type II) ;

– d(u, v) = ∆x(u, v)+d∆y(u,v)2 e ; en ce cas, nous sommes dans la configu-

ration (b) de la Figure 19, et le plus court chemin canonique contientb∆y(u,v)

2 c mouvements diagonaux (type III).

Nous insistons de nouveau que la configuration (b) de la Figure 19 n’estatteignable que pour ∆y(u, v) impair.

Par ailleurs, si u, v est du type II ou du type III, alors on observe qu’uneaugmentation de l’ecart ∆x(u, v) augmente toujours la distance d(u, v) (touten preservant le type). En consequence :

Claim 14. Si la paire u, v est localement eloignee et n’est pas du type I,alors ∆x(u, v) = n.

Sous-graphes isometriques et Regles de reduction

Il est direct qu’une grille classique contient un tres grand nombre de sous-grilles induites, et qu’elles sont isometriques. Cette propriete est preservee,et meme renforcee dans le cas des grilles hexagonales. Nous montreronsdans cette Section comment en deduire des regles de reduction, dont l’objetest de diminuer les dimensions n,m de la grille hexagonale consideree. Cesreductions seront a la base de la caracterisation de l’hyperbolicite pour cettefamille, que nous demontrerons dans la Section suivante. Nous detaillons apresent la structure de la grille hexagonale, au travers des six Claims quisuivent.

64

s s

Fig. 20: Sommet simplicial s sur une ligne du bord.

w s

weak vertex strong vertex

Fig. 21: Categorisation des sommets interieurs sur une colonne du bord.

Le plongement canonique de Hex(n,m) dans le plan est naturellementdelimite par deux lignes et deux colonnes extremales. Ce que nous appel-lerons les bords de la grille. Chaque ligne et chaque colonne du bord s’in-tersectent en un unique sommet (il y en a donc quatre en tout), que nousappellerons un coin. Les sommets restants sur les bords seront appeles som-mets interieurs quand il faudra les differencier d’un coin. Dans un premiertemps, nous proposons une classification plus fine de ces sommets :

Claim 15. Chaque ligne du bord contient un unique sommet simplicial, etce sommet est un coin.

Demonstration. D’abord il est direct qu’un sommet simplicial ne peut etrequ’un coin. Ensuite, il suffit d’observer qu’une ligne ou bien commence avecle carre de la Figure 20 (gauche), ou bien termine avec le carre de la Figure 20(droite).

Il est a noter que tout sommet interieur sur une colonne du bord n’estpas simplicial. Toutefois, on peut quand meme en proposer une classificationen deux categories (voir la Figure 21). Ces appellations de sommets faibleet fort prendront leur sens par la suite. L’idee sous-jacente est que les som-mets faibles pourront etre negliges (substitues par d’autres sommets) pourle calcul de la valeur de l’hyperbolicite, tandis que les sommets forts devronteux etre pris en compte.

De meme que pour les grilles classiques, une sous-grille hexagonale induiteHex(L, l) peut s’obtenir en ne gardant que les lignes de i a i + l, 0 ≤ i ≤i + l ≤ m, et les colonnes de j a j + L, 0 ≤ j ≤ j + L ≤ n. Ce faisant, lagrille hexagonale obtenue est un sous-graphe isometrique, comme le prouvenotre construction des plus courts chemins canoniques.

65

...

...

...

(0,0) (0,1) (0,2) (0,3) (0,4)

(1,0) (1,1) (1,2) (1,3)

(2,0) (2,1) (2,2) (2,3) (2,4)

(3,0) (3,1) (3,2) (3,3)

Fig. 22: La construction du Claim 16. Les sommets etiquetes sont ceux dansH ′. Leur etiquette correspond a leurs coordonnees dans H ′.

Une autre sous-grille interessante, qui cette-fois n’a pas son equivalentdans les grilles classiques, s’obtient par une inversion des roles des aretesverticales et des aretes diagonales dans le graphe. Plus formellement :

Claim 16. Il existe un sous-graphe isometrique H ′ dans Hex(n,m), qui estisomorphe a Hex(n− 1,m) et tel que :

– tous les sommets sur les lignes du bord, a l’exception des deux sommetssimpliciaux du Claim 15, sont dans H ′ ;

– les sommets interieurs des colonnes sont dans H ′ si, et seulement si,ils sont forts.

La construction est directe, ainsi que l’illustre la Figure 22.

A present que nous sommes mieux familiarises avec la structure de la grille,nous pouvons presenter nos regles de reduction mentionnees plus haut.

Soit un quadruplet quelconque a, b, c, d. Nous ecrirons ∆x(a, b, c, d) =maxu,v∈a,b,c,d∆x(u, v), et ∆y(a, b, c, d) = maxu,v∈a,b,c,d∆y(u, v). Claire-ment, ces deux valeurs peuvent etre choisies comme dimensions d’une sous-grille hexagonale et isometrique de Hex(n,m), sur les bords de laquelle lesquatre sommets a, b, c, d sont contenus. En d’autres termes :

Claim 17. δ(a, b, c, d) ≤ δ(Hex(∆x(a, b, c, d),∆y(a, b, c, d))).

Notre but est maintenant d’exhiber certaines conditions grace auxquellesla borne superieure du Claim 17 peut-etre amelioree. Meme dans le cas ouces conditions ne seront pas remplies, leur negation nous fournira davantaged’informations sur la disposition du quadruplet a, b, c, d dans le graphe, cequi s’averera tres utile dans la Section suivante.

Claim 18. Etant donnee une ligne du bord, s’il s’y trouve un unique sommetde a, b, c, d, et que c’est un coin, alors :

66

a

x y

a

x y

a

x y

a

x y

Fig. 23: La substitution d’un coin.

δ(a, b, c, d) ≤ max1, δ(Hex(∆x(a, b, c, d),∆y(a, b, c, d)− 1)).En d’autres termes, cette ligne peut etre virtuellement supprimee, et le coinremplace par un de ses voisins sur la ligne suivante.

Demonstration. Sans perte de generalite, on supposera que le coin susmen-tionne est le sommet a du quadruplet. D’abord, observons que le coin apossede au plus deux voisins sur la ligne suivante : exactement un s’il estsimplicial, et deux sinon. Par ailleurs, pour tout sommet v qui n’est pas surla ligne du bord (celle qui contient le coin), on peut toujours trouver un pluscourt chemin entre v et a qui passe par un des voisins du coin sur la lignesuivante (voir la Figure 23).

Une premiere consequence est que si le coin a est simplicial, alors leprobleme se reduit au cas d’un sommet pendant (de degre 1), ce qui revienta ce que a peut etre substitue par son unique voisin x sur la ligne suivanteet que, ce faisant δ(a, b, c, d) = δ(x, b, c, d).

Dans un second temps, on suppose que le coin n’est pas simplicial. Etantdonne que ses deux voisins sur la ligne suivante sont adjacents, le probleme sereduit cette fois a celui d’un triangle avec une arete-separatrice (voir les Sec-tions 3 et 5). Soient x, y les deux voisins de a sur la ligne suivante (comme in-dique sur la Figure 23). D’apres le Lemme 18, une condition necessaire pourque l’hyperbolicite d’un quadruplet de type (a|b1, b2, b3) soit plus grande quecelle de Hex(n,m− 1) (i.e. la grille hexagonale privee de sa premiere ligne)est que pour un des sommets du triplet des bi, disons b2, tous les plus courtschemins entre b2 et a passent par x. Or, cette propriete ne peut etre verifieeque pour b2 = x, puisque le sommet x est domine par le sommet y (ou, demaniere equivalente, N(x)∪ x ⊆ N(y)∪ y). Par ailleurs, si x ∈ b, c, dalors, d’apres le Lemme 5, on a δ(a, b, c, d) ≤ d(a, x) = 1.

D’ou finalement, puisque ∆y(x, b, c, d) = ∆y(y, b, c, d) = ∆y(a, b, c, d)− 1dans ce cas-la, on a δ(a, b, c, d) ≤ max1, δ(Hex(∆x(a, b, c, d),∆y(a, b, c, d)−1)) d’apres le Claim 17.

67

Un autre resultat utile pour la suite, et plus general, sera le Claim 7, dontnous avons donne l’enonce et la preuve dans la Section A.4. Il est adapteaux graphes cop-wins en general, donc a la grille hexagonale en tant quegraphe ponte, puisque tous les graphes pontes sont eux-memes cop-win [1].Nous montrerons comment il s’applique aux colonnes du bord de la grillehexagonale, au meme titre que le Claim 18 s’applique aux lignes.

Finalement, le Claim 19 nous servira dans la suite a nous ramener auClaim 18 ou au Claim 7 chaque fois que c’est possible.

Claim 19. Supposons que sur chacun des bords de la grille, on trouve (aumoins) un sommet de a, b, c, d. Si deux sommets parmi a, b, c, d sont dessommets interieurs d’une meme colonne du bord, alors il existe une ligne dubord dont l’unique sommet dans a, b, c, d est un coin.

Demonstration. Sans perte de generalite, a et b sont des sommets interieursd’une meme colonne du bord. En particulier, ils ne peuvent etre contenusdans aucun autre bord de la grille. On en deduit par hypothese que la colonneet les deux lignes du bord restantes contiennent chacune un sous-ensemblenon-vide de c, d. En particulier, deux de ces bords doivent contenir lememe sommet, disons c, ce qui implique que c est un coin. Finalement,puisque les lignes du bord n’ont aucun sommet en commun, alors par hy-pothese la ligne du bord opposee a celle de c contient le sommet d et ainsi,c est l’unique sommet dans a, b, c, d sur sa ligne.

Calcul de l’Hyperbolicite

L’hyperbolicite des grilles hexagonales n’avait ete que tres brievementetudiee dans [46], ou les auteurs avaient montre que δ(Hex(2p, 2p)) ≥ p.Nous sommes maintenant en mesure de prouver le resultat suivant :

Proposition 42. δ(Hex(n,m)) = minn,m2 .

Cette valeur est a comparer avec l’hyperbolicite des grilles classiques, quiest deux fois plus grande que pour les grilles hexagonales (voir le Lemme 7).Le reste de la Section est devolu a la preuve de la Proposition 42.

La borne inferieure s’obtient facilement comme suit.

Claim 20. δ(Hex(n,m)) ≥ minn,m2 .

Demonstration. Soit l = minn,m. Considerons la sous-grille hexagonaleet isometrique formee des l premieres lignes et des l premieres colonnes.Soient a, b, c, d les quatre coins de la sous-grille. Les distances qui sont as-sociees a ce quadruplet sont alors : l pour chacun des quatre bords, l+b l2c et

68

l+ d l2e pour les coins qui sont diametralement opposes dans le sous-graphe.D’ou : δ(a, b, c, d) = [(l+ b l2c) + (l+ d l2e)− 2l]/2 = (b l2c+ d l2e)/2 = l/2.

La preuve de la borne superieure δ(Hex(n,m)) ≤ minn,m2 est une

recurrence sur N = n+m.Nous commencerons toutefois par une preuve directe dans le cas ou

minn,m ≤ 1. En effet, quand minn,m = 0, nous sommes dans le casdegenere d’un chemin, donc d’un arbre, et la preuve est triviale. Quandminn,m = 1, la caracterisation de Chepoi et al. s’applique (Theoreme 12)et la 1/2-hyperbolicite du graphe s’en deduit. En fait, une telle grille hexa-gonale est forcement un graphe planaire exterieur et ainsi, la preuve peutmeme etre simplifiee en utilisant le Lemme 33 au lieu du Theoreme 12.

Si N ≤ 3, alors minn,m ≤ 1, et la borne superieure s’en deduitdu paragraphe precedent. Donc, les cas de base de notre recurrence sontdemontres. Dans la suite on supposera N ≥ 4. Si minn,m ≤ 1, alors laborne superieure est directe par l’utilisation du paragraphe precedent. Onajoutera donc comme hypothese minn,m ≥ 2 pour la suite de la preuve.

Soient deux paires localement eloignees u1, v1 et u2, v2 qui satisfont lesconditions du Lemme 4. Si ∆x(u1, v1, u2, v2) < n ou ∆y(u1, v1, u2, v2) < malors on conclut d’apres le Claim 17 en utilisant l’hypothese de recurrence(car N ′ = ∆x(u1, v1, u2, v2) + ∆y(u1, v1, u2, v2) < N). On prendra ainsi,comme troisieme hypothese, ∆x(u1, v1, u2, v2) = n et ∆y(u1, v1, u2, v2) = m.

Enfin, si deux sommets parmi u1, v1, u2, v2 sont des sommets interieursd’une meme colonne du bord, alors d’apres le Claim 19, le Claim 18 s’ap-plique et ainsi, nous pouvons a nouveau conclure en utilisant l’hypothese derecurrence : δ(u1, v1, u2, v2) ≤ max1, δ(Hex(n,m− 1) ≤ minn,m/2. Enconsequence de quoi, notre quatrieme et derniere hypothese pour la suitesera que, quelle que soit la colonne du bord consideree, il existe au plus unsommet parmi u1, u2, v1, v2 qui en est un sommet interieur.

Deux cas sont a distinguer, selon qui de n ou m est le minimum.

Cas ou m ≤ n. Dans un premier temps, supposons qu’au moins une paireparmi u1, v1 et u2, v2 est du type I pour les distances (voir le Claim 13). Alors,d’apres le Lemme 5, on a que δ(u1, v1, u2, v2) ≤ mind(u1, v1), d(u2, v2)/2 ≤∆y(u1, v1, u2, v2)/2 ≤ m/2.

Dans un second temps, si nous supposons qu’aucune des paires u1, v1 etu2, v2 n’est du type I pour les distances, alors d’apres le Claim 14 on a que∆x(u1, v1) = ∆x(u2, v2) = n. En consequence de quoi, il doit y avoir exacte-ment deux sommets du quadruplet sur chaque colonne du bord, dont au plus

69

un seul des deux est interieur d’apres notre quatrieme hypothese. Puisque∆y(u1, u2, v1, v2) = m, on en deduit aussi que pour chaque ligne du bord, aumoins un coin de celle-ci est un sommet dans u1, u2, v1, v2. Comme d’apresce qui precede, on peut associer a chaque sommet du quadruplet une colonnedu bord qui le contient, donc une ligne du bord dont (au moins) deux dessommets sont contenus dans l’ensemble u1, u2, v1, v2 est telle que ses deuxcoins sont contenus dans cet ensemble.On en arrive ainsi a ce que, ou bien les quatre sommets u1, u2, v1, v2 cor-respondent exactement aux quatre coins de la grille, ou bien le Claim 18s’applique. Dans le premier cas, les trois sommes S1, S2 et S3 pour l’hy-perbolicite des quatre coins du graphe valent respectivement 2n (pour leslignes), 2m (pour les colonnes), et 2n+ bm2 c+ dm2 e = 2n+m (pour les dia-gonales). En d’autres termes : δ(u1, u2, v1, v2) = [(2n + m) − 2n]/2 = m/2dans ce cas-la. Dans le second cas, on peut supprimer une ligne du bord etconclure en utilisant l’hypothese de recurrence.

Cas ou m > n. Dans un premier temps, supposons qu’aucun sommetfaible n’est contenu dans les sommets u1, u2, v1, v2. En d’autres termes,chaque sommet du quadruplet est ou bien fort, ou bien sur une ligne dubord. En outre, on se propose de substituer dans le quadruplet chaque som-met simplicial sur une ligne du bord par son unique voisin sur la memeligne. D’apres le Claim 15, cette substitution advient au plus deux fois. Ellen’est alors qu’une application directe du Lemme 20, ce dont nous deduisonsque nos operations de substitution n’ont pu faire diminuer la valeur pourl’hyperbolicite que d’au plus 1/2.L’interet de ces operations est qu’a present, tous les sommets du quadru-plet sont contenus dans une copie isometrique de Hex(n− 1,m), d’apres leClaim 16. Donc on peut utiliser l’hypothese de recurrence pour conclure queδ(u1, u2, v1, v2) ≤ minn− 1,m/2 + 1/2 ≤ (n− 1)/2 + 1/2 ≤ n/2.

Dans un second temps, supposons sans perte de generalite que u1 estfaible. Clairement, il y a un sommet u′1 sur la colonne jouxtant celle de u1,qui est adjacent a u1 et qui domine u1 (voir la Figure 21).Donc, si aucun autre sommet parmi v1, u2, v2 n’est sur la meme colonne dubord que le sommet u1 alors, de facon similaire a ce que nous avions fait pourles sommets simpliciaux, nous remplacons u1 par u′1 dans le quadruplet. Cefaisant, on a d’apres le Claim 7 que δ(u1, v1, u2, v2) ≤ δ(u′1, v1, u2, v2) + 1/2.Par ailleurs, une colonne a ete virtuellement supprimee dans la manoeuvre.Ce dont on deduit δ(u1, u2, v1, v2) ≤ δ(u′1, v1, u2, v2) + 1/2 ≤ δ(Hex(n −1,m)) + 1/2 ≤ (n− 1)/2 + 1/2 ≤ n/2 d’apres l’hypothese de recurrence.

70

Dans le cas contraire, soit v un sommet parmi u2, v1, v2 qui est sur la memecolonne du bord que le sommet u1. Comme u1 est un sommet interieur,donc la paire u1, v n’est pas localement eloignee, et nous supposerons sansperte de generalite v = v2. De plus, le sommet v2 est un coin d’apres notrequatrieme hypothese. En particulier, si v2 est l’unique sommet dans u2, v1, v2

sur la ligne du bord qui le contient, alors le Claim 18 s’applique, et nouspouvons conclure en utilisant l’hypothese de recurrence.Sinon, soit v′ un autre sommet dans u2, v1 contenu sur la meme ligne dubord que le sommet v2. Nous remarquons que lorsque v′ n’est pas lui-memeun coin, alors par elimination, le dernier sommet u parmi u2, v1 doit etrecommun a la ligne et a la colonne du bord restantes, dont il est le seul sommetpresent dans le quadruplet. En d’autres termes, le Claim 18 s’applique ausommet u, et nous pouvons conclure une fois de plus en utilisant l’hypothesede recurrence.Enfin, dans le cas ou v′ est egalement un coin, alors ou bien le dernier sommetrestant dans le quadruplet est encore un coin, auquel cas on se ramene ausous-cas ci-dessus, ou bien le coin v′ est l’unique sommet sur la colonne dubord qui le contient (puisque, dans tous les cas, le sommet u′ doit etre surla ligne du bord opposee). Mais alors, dans ce dernier cas, nous pretendonsque v′ est necessairement domine par un sommet de la colonne qui jouxte lasienne. La preuve est directe si v′ est simplicial. Dans le cas contraire, v′ estune extremite de l’unique diagonale du carre qui le contient (ou, de maniereequivalente, de la corde du C4 induit dont il fait partie), et il est facile devoir que l’autre extremite de cette arete domine effectivement le sommet v′.Alors, au lieu de substituer u1, il suffit a present de substituer v′ dans lequadruplet, et on conclut de meme.

Distortion de l’Hyperbolicite sous l’influence de contractionsd’aretes

Dans cette derniere Section, nous proposons une application etonnantede l’hyperbolicite des grilles hexagonales.

Rappelons pour commencer ce que nous entendons ici par contraction.Etant donne un graphe G = (V,E), soit e = x, y ∈ E une arete de G.Le graphe G/e s’obtient depuis G d’abord en supprimant les sommets x, ydu graphe, puis en ajoutant un nouveau sommet ve dont le voisinage sera(N(x)∪N(y))\x, y. C’est cette operation que nous appellerons contractiond’une arete.

Clairement, les contractions diminuent l’ordre du graphe. C’est pourcette raison qu’il a ete recemment propose dans [45] de s’en servir dans une

71

heuristique pour le calcul de l’hyperbolicite du graphe. Les auteurs dans [45]pretendent que leur methode, dont une description plus lache est donneedans la suite, preserve l’ordre de grandeur du parametre : un graphe de faiblehyperbolicite le reste apres leur transformation, et de meme pour un graphede tres grande hyperbolicite. Pour autant, aucun argument theorique n’a eteavance pour le prouver. Notre but sera de donner les premieres reponses ace probleme.

Distortion additive des suites d’une seule contraction

Notre premier objectif est de determiner ce qui peut advenir quand uneseule arete est contractee. On en deduira nos premieres bornes pour le casgeneral, a une multiplication pres par le nombre de contractions effectuees.Bien que plus simple que le cas general, le cas d’une unique contractionreserve deja des suprises. Ainsi, nous montrerons que la valeur de l’hyper-bolicite peut augmenter des suites d’une contraction.

Proposition 43. La double inegalite suivante est satisfaite : δ(G) − 1 ≤δ(G/e) ≤ δ(G) + 1/2. Par ailleurs, les deux bornes sont atteintes, et ce pourune infinite de graphes.

Demonstration. Soit φ l’application de V dans V (G/e) telle que φ(x) =φ(y) = ve et, pour tout autre sommet u, φ(u) = u. La fonction φ nesert donc qu’a formaliser le resultat de la contraction : deux sommets ontete fusionnes en un seul. Clairement, pour tout sommet u, v ∈ V , on aque dG/e(φ(u), φ(v)) ≤ dG(u, v) ≤ dG/e(φ(u), φ(v)) + 1. Par consequent, ladouble-inegalite δ(G)− 1 ≤ δ(G/e) ≤ δ(G) + 1 est satisfaite.

Supposons a present δ(G/e) = δ(G) + 1. D’abord, rappelons que lesgraphes 0-hyperboliques sont exactement ceux dont les composantes bicon-nexes sont des sous-graphes complets ; ils sont donc stables par l’operationde contraction. On en deduit δ(G) > 0.Soit a, b, c, d un quadruplet tel que δ(φ(a), φ(b), φ(c), φ(d)) = δ(G/e). Noussupposons sans perte de generalite : d(a, b) + d(c, d) ≥ d(a, c) + d(b, d) ≥d(a, d) + d(b, c).De plus, dans le cas ou d(a, c) + d(b, d) = d(a, d) + d(b, c), on impose que :d(φ(a), φ(c)) + d(φ(b), φ(d)) ≥ d(φ(a), φ(d)) + d(φ(b), φ(c)).Alors, pour que la valeur de l’hyperbolicite augmente de 1, il faut que lasomme mediane diminue de 2 et que la plus grande somme ne diminue pas.En clair :

– δ(a, b, c, d) = δ(G),– et d(φ(a), φ(b)) + d(φ(c), φ(d)) = d(a, b) + d(c, d),

72

– et d(φ(a), φ(c)) + d(φ(b), φ(d)) = d(a, c) + d(b, d)− 2,– et d(φ(a), φ(c)) + d(φ(b), φ(d)) ≥ d(φ(a), φ(d)) + d(φ(b), φ(c)).

Il s’ensuit que :d(φ(a), φ(b)) = d(a, b),d(φ(c), φ(d)) = d(c, d),d(φ(a), φ(c)) = d(a, c)− 1et d(φ(b), φ(d)) = d(b, d)− 1.En particulier, d(a, c) = d(a, x, y) + d(c, x, y) + 1et d(b, d) = d(b, x, y) + d(d, x, y) + 1.Mais alors :d(a, c)+d(b, d) = (d(a, x, y)+d(b, x, y)+1)+(d(c, x, y)+d(d, x, y)+1)≥ d(a, b) + d(c, d) et ainsi, δ(a, b, c, d) = δ(G) = 0. Une contradiction. On adonc montre par l’absurde que δ(G/e) ≤ δ(G) + 1/2.

D’apres le Lemme 6, un cycle d’ordre 4(n + 1) a comme hyperboliciten+ 1, tandis qu’un cycle d’ordre 4n+ 3 a comme hyperbolicite n ; ainsi, laborne inferieure est atteinte. De meme, d’apres le Lemme 6, un cycle d’ordre4n+1 a comme hyperbolicite n−1/2, tandis que le cycle d’ordre 4n a commehyperbolicite n ; ainsi, la borne superieure est atteinte egalement.

Distortion des suites de la contraction d’un couplage

Un couplage est un ensemble d’aretes dont les extremites sont deux-a-deux disjointes. Dans une version simplifiee, l’heuristique proposee dans [45]revient a diminuer l’ordre du graphe par une application repetee de cetteroutine :

– Trouver un couplage maximal M du graphe ;– Contracter toutes les aretes dans M .

Nous appellerons G′ le graphe G/M qui en resulte, et notre ambition estde borner le ratio δ(G)

δ(G′) (dans le pire des cas). En fait, a proprement parler,le ratio ne peut pas etre borne superieurement, puisqu’il est possible danscertains cas que G′ soit un cactus de cliques (donc d’hyperbolicite 0 : prendrele cas simple du C4 pour s’en convaincre).

Nous donnons a present un argument simple qui montre pourquoi ce casdegenere (i.e. δ(G′) = 0) n’est pas possible au-dela d’une valeur limite pourl’hyperbolicite. En effet, soit tl(G) la longueur d’arborescence du graphe G(ou tree-length, voir la Section D pour rappel de la definition). Clairement,les distances dans G′ sont, au moins, egales a (la partie entiere inferieure de)la moitie des distances originales dans G. Aussi, on a que tl(G) ≤ 2tl(G′)+1.Or, il a ete prouve dans [19] que δ(G) ≤ tl(G) ≤ (12 + 8 log n)δ(G) + 17. En

73

Fig. 24: La contraction du couplage Mn de la grille.

particulier, si δ(G) ≥ 37, alors de meme tl(G) ≥ 37 et donc, tl(G′) ≥ 18, cequi rend impossible que δ(G′) = 0.

Il est a noter qu’en pratique, on connaıt seulement des graphes G quisont 1-hyperboliques pour lesquels G′ est un block-graph. Dans la suite, onsupposera l’hyperbolicite de G suffisamment grande pour que le cas degenereδ(G′) = 0 soit evite.

Proposition 44. maxG,Mδ(G)δ(G′) ≥ 5.

De plus, pour tout n ≥ 1, il existe un couplage maximal Mn de la grillecarree (n+1)×(n+1) (notee Gn) tel que le rapport δ(Gn)

δ(G′n) tend vers 4 quandn tend vers l’infini.

Demonstration. Le couplage Mn est defini comme suit.– D’abord on fixe une carte planaire pour la grille Gn, plus une orienta-

tion pour celle-ci.– On numerote les lignes de 0 a n, du haut vers le bas.– Pour chaque ligne, on numerote les aretes de 1 a n, de la gauche vers

la droite.– Si la ligne a un numero pair, alors on ajoute dans Mn toutes ses aretes

de numero impair (1, 3, . . .).– Sinon, on ajoute dans Mn toutes ses aretes de numero pair (2, 4, . . .).

Il peut etre verifie quand n est pair que G′n est isomorphe a la grillehexagonale Hex(n2 , n), d’hyperbolicite n/4 d’apres la Proposition 42.

Quand n est impair, G′n est un sous-graphe isometrique de Hex(dn2 e, n)qui contient lui-meme Hex(bn2 c, n) comme sous-graphe isometrique (voir laFigure 24). D’ou :n−1

4 ≤ bn2c

2 ≤ δ(G′n) ≤ d

n2e

2 ≤n+1

4 d’apres la Proposition 42.En pratique, nous avons observe que la borne superieure etait toujours at-teinte quand n ≡ 3 mod 4, et la borne inferieure toujours atteinte quandn ≡ 1 mod 4.

74