Every $k$-Quasi-Planar Graph Has Linearly Many Edges

Ankan Sadhu

Résumé IA · arXiv: 2611.01509v1 · math.CO

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

Ankan Sadhu

L’essentiel

L’article prouve que, pour tout k fixé, un graphe simple dessiné sans k arêtes deux à deux croisées possède au plus Cₖn arêtes, même si deux arêtes peuvent se croiser plusieurs fois.

D’après l’abstract uniquement : vérifiez les détails dans l’article original.

Question

Combien d’arêtes peut avoir un graphe simple dessiné dans le plan lorsqu’aucun ensemble de k arêtes ne se croise deux à deux ? Le résultat s’applique-t-il aussi aux dessins où deux arêtes ont plusieurs croisements, y compris lorsqu’elles partagent une extrémité ?

Méthode

Pour n ≥ 3, les auteurs retirent un petit disque autour de chaque sommet et représentent les arêtes par des arcs sur une sphère à n trous. Ces arcs sont essentiels et deux à deux non homotopes; les familles de relèvements deux à deux intersectants ont taille au plus k−1, ce qui permet d’appliquer le théorème de Beeker et Lazarovich sur les motifs de surface, avec une triangulation dont le nombre d’arêtes et de triangles est linéaire en n.

Résultats

Résultat Pour tout entier k ≥ 2 fixé, le nombre d’arêtes est au plus Cₖn, où Cₖ dépend seulement de k.
Résultat La borne s’applique même si deux arêtes peuvent se croiser plusieurs fois, y compris lorsqu’elles ont une extrémité commune.
Voir le passage dans l’article
We allow any finite number of proper crossings between two edges, including edges with a common endpoint.
Résultat Dans la transformation en arcs sur la sphère à n trous, les arcs associés à des arêtes différentes sont essentiels et deux à deux non homotopes.
Voir le passage dans l’article
The arcs are therefore essential and pairwise nonhomotopic, with endpoints allowed to move along their boundary circles during a homotopy.
Interprétation des auteurs La borne linéaire découle du théorème sur les motifs de surface et d’une triangulation de taille linéaire.
Voir le passage dans l’article
Beeker and Lazarovich's theorem on surface patterns then bounds the number of arcs. Their estimate is linear in the size of a triangulation, and an explicit triangulation of the $n$-holed sphere has linearly many edges and triangles.

Limites

Le résultat porte sur les graphes simples dessinés dans le plan et sur les valeurs fixes de k avec k ≥ 2; il ne précise pas ici les constantes Cₖ.

Portée

Le résultat établit une borne linéaire en n pour les graphes quasi-planaires, sans supposer que deux arêtes se croisent au plus une fois. Il relie ce problème aux bornes sur les familles d’arcs dans les surfaces.

Rédigé par une IA à partir de l’article. Les passages cités sont vérifiés mot pour mot dans le texte analysé ; le reste peut contenir des erreurs.

Mots clés générés par l'IA : quasi-planarité graphes dessinés croisements d’arêtes arcs sur les surfaces borne linéaire

Pour aller plus loin

Résumé Complet
Résumé vulgarisé
Article de blog
Abstract original

L’article d’Ankan Sadhu, intitulé « Every k-Quasi-Planar Graph Has Linearly Many Edges », étudie une question de combinatoire géométrique : combien d’arêtes peut contenir un graphe simple à $n$ sommets dessiné dans le plan lorsqu’aucun ensemble de $k$ arêtes ne se croise deux à deux ? Pour tout entier fixe $k \geq 2$, le résultat principal établit une borne linéaire en $n$. Il existe une constante $C_k$, qui ne dépend que de $k$, telle que le graphe possède au plus $C_k n$ arêtes. Le résumé de l’article ne précise pas la valeur de cette constante. Le cadre considéré autorise des dessins relativement généraux : deux arêtes peuvent se croiser plusieurs fois, et des arêtes ayant une extrémité commune peuvent également se croiser. La restriction concerne les croisements mutuels : il ne doit pas exister $k$ arêtes distinctes dont chaque paire se croise. Le résultat ne suppose donc pas que deux arêtes se croisent au plus une fois. La méthode ramène le problème à l’étude d’arcs sur une surface. Pour $n \geq 3$, on retire un petit disque autour de chaque sommet. On obtient ainsi une sphère percée de $n$ trous, où chaque arête devient un arc reliant deux cercles de bord distincts. Comme le graphe est simple, deux arêtes distinctes ne relient pas la même paire de sommets ; leurs arcs relient donc des paires différentes de cercles. L’article considère ces arcs comme essentiels et deux à deux non homotopes, les extrémités pouvant glisser le long des cercles de bord pendant une homotopie. La méthode utilise ensuite le revêtement universel de la surface. Une famille d’arcs dont les relevés s’intersectent deux à deux donne, après projection, des arêtes distinctes qui se croisent deux à deux dans le dessin du graphe. L’absence de $k$ arêtes mutuellement croisées implique donc qu’une telle famille de relevés contient au plus $k-1$ éléments. Le théorème de Beeker et Lazarovich sur les motifs de surface permet alors de borner le nombre total d’arcs en fonction de cette taille maximale et de celle d’une triangulation de la surface. Cette borne est linéaire par rapport à la taille de la triangulation. Or une triangulation explicite de la sphère à $n$ trous possède un nombre d’arêtes et de triangles linéaire en $n$. En combinant ces résultats, on obtient la borne annoncée : le graphe possède au plus $C_k n$ arêtes. Ainsi, pour chaque valeur fixe de $k$, interdire les croisements mutuels de $k$ arêtes suffit à limiter le nombre d’arêtes à une quantité proportionnelle au nombre de sommets, même lorsque le dessin autorise des croisements répétés. Les informations quantitatives disponibles restent toutefois limitées : seul le titre et le résumé de l’article sont accessibles. Le résumé ne donne ni la valeur explicite de $C_k$, ni les détails techniques des applications du théorème sur les surfaces, ni les éventuelles améliorations ou variantes présentées dans l’article.

Combien d’arêtes peut contenir un graphe sans croisements mutuels ?

Dans un dessin de graphe, les arêtes peuvent se croiser. Mais que se passe-t-il si l’on interdit à un groupe de plusieurs arêtes de se croiser toutes entre elles ? Dans son article Every k-Quasi-Planar Graph Has Linearly Many Edges, Ankan Sadhu étudie cette question et établit un résultat frappant : pour tout entier fixe k ≥ 2, le nombre d’arêtes est proportionnel au nombre de sommets.

Autrement dit, il existe une constante Ck, qui dépend uniquement de k, telle que tout graphe considéré possède au plus Ckn arêtes, où n désigne le nombre de sommets. Le résumé disponible ne précise pas la valeur de cette constante, mais la conclusion générale est claire : l’absence de croisements mutuels entre k arêtes impose une forte limite à la taille du graphe.

Une condition de croisement assez souple

La question porte sur les graphes simples dessinés dans le plan. La condition dite « k-quasi planaire » interdit qu’il existe k arêtes distinctes dont chaque paire se croise. Elle ne signifie pas que le dessin doit être sans croisements, ni même que deux arêtes ne peuvent se croiser qu’une seule fois.

Le cadre est donc plus général que celui de nombreux dessins usuels. Deux arêtes peuvent se rencontrer plusieurs fois, et des arêtes qui partagent un sommet peuvent aussi se croiser. La restriction vise uniquement l’existence d’un ensemble de k arêtes mutuellement croisées. Malgré cette liberté, le résultat de Sadhu montre que le nombre total d’arêtes reste linéaire en n, dès lors que k est fixé.

Transformer le dessin en problème de surface

La stratégie consiste à reformuler le problème à l’aide de la topologie. Pour n ≥ 3, on retire un petit disque autour de chacun des sommets. Le plan, considéré comme une sphère, devient alors une sphère percée de n trous. Chaque arête du graphe se transforme en un arc reliant deux cercles de bord distincts.

La simplicité du graphe joue ici un rôle important : deux arêtes distinctes ne peuvent pas relier la même paire de sommets. Les arcs obtenus relient donc des paires différentes de cercles. L’article les traite comme des arcs essentiels et deux à deux non homotopes. En termes simples, on ne peut pas déformer continûment l’un de ces arcs pour le faire coïncider avec un autre, en laissant les extrémités glisser le long des bords.

Pourquoi examiner le revêtement universel ?

Sadhu utilise ensuite le revêtement universel de la surface, une construction qui permet d’étudier les arcs dans un espace plus simple tout en conservant des informations sur leurs intersections. Une famille de relevés qui s’intersectent deux à deux correspond, après projection sur la surface, à des arêtes distinctes qui se croisent deux à deux dans le dessin initial.

La condition de quasi-planarité limite donc la taille de telles familles : il ne peut pas y avoir k relevés correspondant à k arêtes mutuellement croisées. Chaque famille de ce type contient ainsi au plus k − 1 éléments. Cette observation relie directement la contrainte géométrique du graphe à une propriété des arcs sur la surface.

Du contrôle des intersections à une borne linéaire

Pour passer de cette limite locale à un décompte de toutes les arêtes, l’article s’appuie sur un théorème de Beeker et Lazarovich concernant les motifs de surface. Ce résultat permet de borner le nombre d’arcs en fonction de deux éléments : la taille maximale d’une famille dont les relevés s’intersectent deux à deux, et la taille d’une triangulation de la surface.

La première quantité est contrôlée par k. La seconde est linéaire en n : une triangulation explicite de la sphère à n trous comporte un nombre d’arêtes et de triangles proportionnel au nombre de trous. En combinant ces ingrédients, on obtient donc une borne linéaire sur le nombre d’arcs, et par conséquent sur le nombre d’arêtes du graphe. C’est ainsi qu’apparaît la constante Ck.

La condition géométrique interdit k arêtes mutuellement croisées.
Le dessin est converti en une famille d’arcs sur une sphère percée.
Le revêtement universel traduit les croisements en familles d’intersections contrôlées.
Un théorème sur les motifs de surface fournit le décompte final, linéaire en n.

La portée du résultat et ses limites

Le résultat est remarquable parce qu’il ne repose pas sur une hypothèse restrictive selon laquelle chaque paire d’arêtes ne se croiserait qu’une fois. Même dans des dessins où les croisements peuvent se répéter, interdire les groupes de k arêtes qui se croisent toutes entre elles suffit à limiter le nombre total d’arêtes à une quantité proportionnelle au nombre de sommets.

Les informations disponibles restent toutefois limitées au titre et au résumé de l’article. Elles ne donnent ni la valeur explicite de Ck, ni les détails techniques de l’application du théorème sur les surfaces, ni les éventuelles variantes ou améliorations présentées dans le texte complet. La contribution centrale ressort néanmoins nettement : une contrainte sur les croisements mutuels se traduit, par un détour topologique, en une borne linéaire pour la taille du graphe.

Créé le 09 Nov. 2026

Cette synthèse vous a-t-elle été utile ?

Note : 0

Posez des questions sur cet article à notre assistant IA

Comment discuter avec cet article ? Guide illustré

Comparer avec le PDF

Vous pouvez aussi discutez avec plusieurs papiers à la fois ici.

⚠La licence de l'article ne nous permet pas de nous appuyer sur son contenu et l'assistant IA ne peut se servir que des métadonnées de l'article plutôt que de l'article complet.

Instructions pour utiliser l'assistant IA ?

Outils pour cet article

Expliquer autrement 1 réécriture gratuite restante aujourd'hui

Enregistrer dans une collection Regroupez des articles en collections pour les comparer, les interroger et les exporter. Continuer avec Google Créer un compte gratuit Se connecter

Exporter BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Outils avancés Premium

Pour suivre un domaine de près : alertes de citations, diapositives de journal club, comparaison des versions et envoi vers Zotero. Découvrir Premium

Zotero

Alertes de citation Guide des alertes de citations

Qui travaille dessus ? Les personnes et institutions qui publient sur son sujet

Lettre hebdomadaire Présenté dans « Mathématiques et statistiques cette semaine » du 9 novembre 2026. Mathématiques et statistiques cette semaine : des désordres qui deviennent prévisibles

Journal club Premium+ Des slides pour le présenter Proposer pour le journal club

Versions Ce qui a changé entre les versions

En parler en public Premium+ Kit presse : communiqué, questions, détecteur de hype Guide du kit presse

Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

L’essentiel

Question

Méthode

Résultats

Limites

Portée

Pour aller plus loin

Definitions

Combien d’arêtes peut contenir un graphe sans croisements mutuels ?

Une condition de croisement assez souple

Transformer le dessin en problème de surface

Pourquoi examiner le revêtement universel ?

Du contrôle des intersections à une borne linéaire

La portée du résultat et ses limites

Posez des questions sur cet article à notre assistant IA

Outils pour cet article

Outils avancés Premium

Les articles autour de celui-ci

Les articles les plus proches

Les travaux antérieurs sur lesquels il s’appuie

Aller plus loin

Citer cet article (BibTeX)