Graphique planaire via l'intersection de gros trucs?

14

Il existe un beau théorème de Koebe (voir ici ) qui stipule que tout graphe planaire peut être dessiné comme un graphe de baisers de disques (très romantique ...). (Autrement dit, tout graphique plan peut être dessiné comme le graphique d'intersection des disques.)

Le théorème de Koebe n'est pas très facile à prouver. Ma question: existe-t-il une version plus facile de ce théorème où, au lieu de disques, on est autorisé à utiliser toutes les formes convexes de graisse (la convexité peut être ouverte à des négociations, mais pas de gras). Notez que chaque sommet peut avoir une forme différente.

Merci...

Précision: Pour une forme , laissez - R ( X ) le rayon de la boule englobante plus petit de X , et que r ( X ) me laisser le rayon de la plus grande boule fermée en S . La forme S est α- grasse si R ( x ) / r ( x ) α . (Ce n'est pas la seule définition de l'adiposité, BTW.)XR(X)Xr(X)SSαR(x)/r(x)α

Sariel Har-Peled
la source
être légèrement pédant: le théorème de Koebe concerne les graphes de contact, qui sont légèrement différents des graphes d'intersection. Quelle version preferez-vous ?
Suresh Venkat
Je suppose donc que l'adiposité est requise du fait que chaque graphe planaire est le graphe d'intersection de segments dans le plan (Chalopin & Gonçalves, STOC 09). S'ils ne sont pas gros, les baisers sont les mêmes que l'intersection. (Hm, la dernière phrase est étrange prise hors de son contexte!)
RJK
La graisse rend la vie plus facile pour autant que de faire d'autres choses avec le graphique (par exemple, trouver un séparateur).
Sariel Har-Peled
3
Je me demande si la vraie question ici est: "donner une simple preuve du théorème de Koebe" plutôt que "trouver des familles de formes grasses de faible complexité qui simulent le théorème de Koebe"
Suresh Venkat
2
Sûr. C'est une interprétation valable. Cependant, je pense que pour obtenir une preuve simple du théorème de Koebe, il faut le détendre d'une manière ou d'une autre ...
Sariel Har-Peled

Réponses:

10

Vous n'avez pas dit que les gros objets devaient être bidimensionnels, n'est-ce pas? Felsner et Francis prouvent que c'est toujours possible avec des cubes à axes parallèles en 3D . Mais, la preuve implique les généralisations de Schramm de Koebe-Thurston-Andreev, donc ce n'est pas exactement un résultat plus simple. Ils mentionnent également en cours de route que pour les graphiques planaires maximaux à quatre connexions, il est possible d'utiliser des triangles équilatéraux à côtés parallèles.

David Eppstein
la source
Eh bien, c'est aussi une bonne question, je suppose. Existe-t-il une preuve rapide que chaque graphe planaire est représentable comme le graphe de contact des sphères?
RJK
6

K4

Suresh Venkat
la source
Rectangles parallèles d'axe? Ou des rectangles?
Sariel Har-Peled
rectangles parallèles d'axe.
Suresh Venkat
4

Il y a un nouvel article sur l'arxiv par Duncan, Gansner, Hu, Kaufman et Kobourov sur les représentations des graphes de contact. Ils montrent que des polygones à 6 faces sont nécessaires et suffisants. Les hexagones peuvent être convexes, mais il n'était pas clair pour moi à la première lecture s'ils étaient gros aussi.

Suresh Venkat
la source
Yo yo. Je viens de découvrir ce papier moi-même ... Ils utilisent le résultat de Fraisseix etal mentionné ci-dessus, et un résultat de Kant ...
Sariel Har-Peled
Ici, «contact» est défini différemment. Le contact ponctuel est interdit, d'après ma lecture.
RJK
J'imagine que c'est raisonnable pour les représentations polygonales (car tout contact non-vertex sera nécessairement non-ponctuel)?
Suresh Venkat
Puisqu'il n'y a ici que trois slops autorisés, le toucher doit se faire par des bords parallèles se touchant ... Non?
Sariel Har-Peled
0

Gerd Wegner dans sa thèse de doctorat (Georg-August-Universität, Göttingen, 1967) a prouvé que tout graphique est le graphique de contact d'un ensemble de polytopes convexes tridimensionnels (mais il attribue la première preuve non publiée du résultat à Grünbaum). Ceci est une courte preuve.

RJK
la source
Il existe des preuves directes faciles de cela, par exemple en plaçant des points sur la courbe des moments et en calculant leur diagramme de Voronoï. Ici, la condition d'adiposité échoue lamentablement ...
Sariel Har-Peled
Ah, j'ai complètement mal compris "gras". Je suis gêné d'admettre (mais je suppose que cela doit être clair maintenant) que je ne connaissais pas la définition, jusqu'à ce que je google "gros triangle". Pourriez-vous s'il vous plaît fournir une référence / définition pour ce concept?
RJK
De plus, la représentation que je mentionne peut être utilisée pour représenter n'importe quel graphique de cette manière - pas seulement des graphiques planaires.
Sariel Har-Peled
Merci pour la clarification de "gras" dans la question. Il convient de noter que je n'ai pas non plus mentionné planaire dans ce post. Pour une valeur d'adiposité donnée, chaque graphique est représentable par des polytopes convexes de graisse dans une dimension (assez élevée). La question évidente est de savoir si la dimension liée peut être uniforme sur tous les graphiques. Cela a-t-il été étudié?
RJK
Pas autant que je sache, mais je ne connais pas très bien ce genre de choses ...
Sariel Har-Peled