Graphe gradué planaire
Chers lecteurs,
Y a-t-il des résultats sur la planarité des graphes dans le cas des graphes gradués ? Le sens de la question n'est pas limpide alors j'explique.
En fait, il faut savoir que je ne connais absolument rien à la théorie de graphes.
Pour "graphe gradué" j'explique avec un exemple. Par exemple, un graphe gradué à 3 niveaux. C'est-à-dire que l'ensemble des sommets $V$ s'écrit $V=V_0 \cup V_1 \cup V_2$, que l'ensemble des arêtes s'écrit $E= E_1 \cup E_2$, avec $E_1$ qui relie les $v_0 \in V_0$ à des $v_1\in V_1$ et $E_2$ qui relie les $v_1 \in V_1$ à des $v_2\in V_2$. Par exemple ce graphe que je viens de dessiner à l'arrache avec Paint, graphe pour lequel $V_0=\{1\}$, $V_1=\{1,2\}$, $V_2=\{1,2,3\}$.
Sur mon dessin, les arêtes ne se croisent pas mais elles se croiseraient si j'échangeais le sommet 1 avec le sommet 3 dans $V_2$.
Le mot "planarité" dans ma question n'est pas approprié car la question que je me pose est bien plus précise que la planarité : je me demande s'il existe une représentation planaire du graphe mais qui a la même structure de "graduation".
Autrement dit peut-être que la question peut se formuler ainsi : existe-t-il des ordres sur les $V_i$ (qui sont toujours des ensembles finis) tels que si je dessine les $v \in V_{i-1}$ dans cet ordre sur une droite et les $v' \in V_{i}$ sur une droite parallèle alors au sein des $E_i$ aucune arête ne se croise ?
Attention, ce n'est pas (a priori) un problème qui se ramène à un problème sur chaque paire $\{V_{i-1}, V_i\}$ car ça doit se "raccorder".
J'espère que la question est compréhensible, sinon j'espère que vous ne manquerez pas de me le faire savoir.
Y a-t-il des résultats sur la planarité des graphes dans le cas des graphes gradués ? Le sens de la question n'est pas limpide alors j'explique.
En fait, il faut savoir que je ne connais absolument rien à la théorie de graphes.
Pour "graphe gradué" j'explique avec un exemple. Par exemple, un graphe gradué à 3 niveaux. C'est-à-dire que l'ensemble des sommets $V$ s'écrit $V=V_0 \cup V_1 \cup V_2$, que l'ensemble des arêtes s'écrit $E= E_1 \cup E_2$, avec $E_1$ qui relie les $v_0 \in V_0$ à des $v_1\in V_1$ et $E_2$ qui relie les $v_1 \in V_1$ à des $v_2\in V_2$. Par exemple ce graphe que je viens de dessiner à l'arrache avec Paint, graphe pour lequel $V_0=\{1\}$, $V_1=\{1,2\}$, $V_2=\{1,2,3\}$.
Sur mon dessin, les arêtes ne se croisent pas mais elles se croiseraient si j'échangeais le sommet 1 avec le sommet 3 dans $V_2$.
Le mot "planarité" dans ma question n'est pas approprié car la question que je me pose est bien plus précise que la planarité : je me demande s'il existe une représentation planaire du graphe mais qui a la même structure de "graduation".
Autrement dit peut-être que la question peut se formuler ainsi : existe-t-il des ordres sur les $V_i$ (qui sont toujours des ensembles finis) tels que si je dessine les $v \in V_{i-1}$ dans cet ordre sur une droite et les $v' \in V_{i}$ sur une droite parallèle alors au sein des $E_i$ aucune arête ne se croise ?
Attention, ce n'est pas (a priori) un problème qui se ramène à un problème sur chaque paire $\{V_{i-1}, V_i\}$ car ça doit se "raccorder".
J'espère que la question est compréhensible, sinon j'espère que vous ne manquerez pas de me le faire savoir.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Il y a un plein d' études de cas avec algo. associés comme là:
Décompositions arborescentes de graphes avec heuristiques.
http://tel.archives-ouvertes.fr/docs/00/48/06/55/PDF/maindoc.pdf
J'espère, sinon, avoir saisi peu ou prou le sens de ta requète...
Dit autrement, le graphe $K_{3,3}$ n'est pas planaire.
C'est le problème classique des trois maisons qu'on veut relier simultanément au gaz, à l'eau et à l'électricité.
Cordialement,
Rescassol
La réponse à quoi est non ? Ce que je veux savoir c'est s'il existe des caractérisations des cas pour lesquels c'est vrai, des trucs comme ça.