Every $k$-Quasi-Planar Graph Has Linearly Many Edges
Auteurs : Ankan Sadhu
Résumé scientifique
For every fixed integer $k\ge2$, we prove that every simple graph on $n$ vertices drawn in the plane with no $k$ pairwise crossing edges has at most $C_kn$ edges, where $C_k$ depends only on $k$. We allow any finite number of proper crossings between two edges, including edges with a common endpoint. For $n\ge3$, removing a small disk around each vertex turns the drawing into a family of arcs on a sphere with $n$ boundary circles. Each arc joins two different boundary circles, and different edges have different unordered pairs of endpoint circles. The arcs are therefore essential and pairwise nonhomotopic, with endpoints allowed to move along their boundary circles during a homotopy. Any family of pairwise intersecting lifts to the universal cover projects to distinct graph edges that cross pairwise. Its size is consequently at most $k-1$. 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.
Les articles autour de lui, par date et par proximité
Plus haut, c’est plus proche de cet article ; à gauche, c’est plus ancien. Les traits relient les articles proches entre eux : les groupes de traits sont des sous-thèmes. Sélectionnez un point pour voir pourquoi il est là. Retour au résumé de cet article
Les articles autour de celui-ci
Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.
Les articles les plus proches
-
On the number of edges in quasiplanar graphsJ. Pach, G. Tardos, Ji Zeng · 2026 · Pas encore résumé
« On the number of edges in quasiplanar graphs » présente une preuve simplifiée de la borne linéaire conjecturée pour les graphes sans k arêtes deux à deux croisées.
Résumé scientifique
A $k$-quasiplanar graph is a graph drawn in the plane with no $k$ pairwise crossing edges. Pach, Shahrokhi, and Szegedy conjectured that every such graph on $n$ vertices has $O_k(n)$ edges. ChatGPT produced a proof of this conjecture. Here, we present a simplified, self-contained version of that proof.
-
New bounds on the maximum number of edges in k-quasi-planar graphsAndrew Suk, Bartosz Walczak · 2013 · Computational geometry · cité 43 fois · Pas encore résumé
« New bounds on the maximum number of edges in k-quasi-planar graphs » améliore les bornes d’arêtes pour les graphes k-quasi-planaires, mais n’obtient pas la borne linéaire générale.
Résumé scientifique
A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A 20-year-old conjecture asserts that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O ( n ) . Fox and Pach showed that every k-quasi-planar graph with n vertices has at most n ( log ? n ) O ( log ? k ) edges. We improve this upper bound to 2 α ( n ) c n log ? n , where α ( n ) denotes the inverse Ackermann function and c depends only on k, for k-quasi-planar graphs in which any two edges intersect in a bounded number of points. We also show that every k-quasi-planar graph with n vertices in which any two edges have at most one point in common has at most O ( n l…
-
Quasi-planar graphs have a linear number of edgesP. Agarwal, B. Aronov, J. Pach et al. · 1995 · International Symposium Graph Drawing and Network Visualization · cité 150 fois · Pas encore résumé
« Quasi-planar graphs have a linear number of edges » étudie la borne linéaire du nombre d’arêtes dans les graphes quasi-planaires.
-
The Exact Number of Pentagons in Book-Free GraphsWen-Tao Hu · 2026 · Pas encore résumé
« The Exact Number of Pentagons in Book-Free Graphs » détermine un extremum de sous-graphes dans les graphes sans livres, plutôt que dans les dessins quasi-planaires.
Résumé scientifique
Let $B_k$ denote the book consisting of $k$ triangles sharing a common edge. We prove that there exist absolute constants $\rho>0$ and $N$ such that, for every pair of integers $n,k$ with $n\ge N$ and $2\le k\le \rho n$, writing $n=5q+r$ with $0\le r<5$, \[ \operatorname{ex}(n,C_5,B_k)=q^{\,5-r}(q+1)^r, \] with the balanced complete $C_5$-blow-ups as the only extremal graphs. The linear order of this range is best possible since for all sufficiently large $n$, the formula fails whenever $k\ge0.14n$.
-
Quasiplanar graphs, string graphs, and the Erdős-Gallai problemJacob Fox, J. Pach, Andrew Suk · 2021 · International Symposium Graph Drawing and Network Visualization · cité 12 fois · Pas encore résumé
« Quasiplanar graphs, string graphs, and the Erdős-Gallai problem » borne le nombre d’arêtes de graphes quasi-planaires, avec une borne dépendant du logarithme.
Résumé scientifique
An $r$-quasiplanar graph is a graph drawn in the plane with no $r$ pairwise crossing edges. Let $s \geq 3$ be an integer and $r=2^s$. We prove that there is a constant $C$ such that every $r$-quasiplanar graph with $n \geq r$ vertices has at most $n\left(Cs^{-1}\log n\right)^{2s-4}$ edges. A graph whose vertices are continuous curves in the plane, two being connected by an edge if and only if they intersect, is called a string graph. We show that for every $\epsilon>0$, there exists $\delta>0$ such that every string graph with $n$ vertices, whose chromatic number is at least $n^{\epsilon}$ contains a clique of size at least $n^{\delta}$. A clique of this size or a coloring using fewer than $…
-
Minimum Label $k$-Cut on Planar Graphs: Complexity and Color StructureYuan-Hao Wang, Wei Wang · 2026 · Pas encore résumé
« Minimum Label k-Cut on Planar Graphs » étudie la complexité d’une coupure colorée sur des graphes planaires, sans analyser les croisements d’arêtes.
Résumé scientifique
Minimum Label $k$-Cut asks for a minimum-size set of colors such that deleting all edges of these colors leaves at least $k$ connected components. We study how the structure of the underlying graph and its color classes affects the complexity of this problem. Regarding fixed-parameter tractability with respect to $k$ on simple planar graphs, we prove that the problem is W[1]-hard, even when the underlying graph is a cactus graph and each color appears at most twice. Furthermore, for cactus graphs in which every color class is connected, we establish a complexity boundary in terms of the maximum monochromatic degree: when this degree is at most two, an optimal solution can be found in $O(Nk^2…
-
Smallest Cubic Non-1-Planar GraphsS. Pupyrev · 2026 · arXiv.org · preprint, non relu par les pairs · Pas encore résumé
« Smallest Cubic Non-1-Planar Graphs » caractérise des graphes qui ne peuvent être dessinés avec au plus un croisement par arête.
Résumé scientifique
A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graph…
-
Coloring Curves that Cross a Fixed CurveAlexandre Rok, Bartosz Walczak · 2015 · International Symposium on Computational Geometry · cité 14 fois · Pas encore résumé
« Coloring Curves that Cross a Fixed Curve » déduit une borne O(n log n) pour les graphes k-quasi-planaires où deux arêtes se croisent au plus t fois.
Résumé scientifique
We prove that for every integer $$t\geqslant 1$$t⩾1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is $$\chi $$χ-bounded. This is essentially the strongest $$\chi $$χ-boundedness result one can get for those kind of graph classes. As a corollary, we prove that for any fixed integers $$k\geqslant 2$$k⩾2 and $$t\geqslant 1$$t⩾1, every k-quasi-planar topological graph on n vertices with any two edges crossing at most t times has $$O(n\log n)$$O(nlogn) edges.
Les travaux antérieurs sur lesquels il s’appuie
-
Relaxing Planarity for Topological GraphsJ. Pach, R. Radoičić, G. Tóth · 2002 · JCDCG · cité 57 fois · Pas encore résumé
« Relaxing Planarity for Topological Graphs » est un chapitre de synthèse sur les généralisations de la planéité pour les graphes topologiques.
Résumé scientifique
Note: Professor Pach's number: [175]; Also in: More Sets, Graphs and Numbers, E. Gy{\Ho}ri, G.O.H. Katona, L. Lovasz (eds.), Bolyai Society mathematical studies, 15, Budapest, 2006, 559-576 Reference DCG-CHAPTER-2008-029 Record created on 2008-11-18, modified on 2017-05-12
-
On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing EdgesEyal Ackerman · 2006 · SCG '06 · cité 99 fois · Pas encore résumé
« On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing Edges » porte sur le nombre maximal d’arêtes sous une contrainte de croisements.
-
A parity Erd\H{o}s-Hajnal theorem for $t$-intersecting curvesAndrew Suk, Su Zhou · 2026 · cité 1 fois · Pas encore résumé
« A parity Erdős-Hajnal theorem for t-intersecting curves » étudie des sous-familles de courbes dont les intersections ont une parité uniforme.
Résumé scientifique
For every fixed $t\ge 1$, we prove a parity analogue of the mighty Erd\H{o}s-Hajnal property for $t$-intersecting curves in the plane. Let $\mathcal B$ be a set of blue curves and $\mathcal G$ a set of green curves in the plane such that $\mathcal B\cup\mathcal G$ is a collection of $t$-intersecting curves in general position. We show that there exist subfamilies $\mathcal B'\subseteq\mathcal B$ and $\mathcal G'\subseteq\mathcal G$ such that $|\mathcal B'|\geq \varepsilon|\mathcal B|$ and $|\mathcal G'|\geq \varepsilon|\mathcal G|$, where $\varepsilon>0$ depends only on $t$, such that either every pair in $\mathcal B'\times\mathcal G'$ intersects an even number of times or every such pair in…
-
Cubical accessibility and bounds on curves on surfacesB. Beeker, Nir Lazarovich · 2017 · Journal of Topology · cité 6 fois · Pas encore résumé
« Cubical accessibility and bounds on curves on surfaces » établit des bornes sur des courbes dans les surfaces, mais par des méthodes de cubulation.
Résumé scientifique
We bound the size of d ‐dimensional cubulations of finitely presented groups. We apply this bound to obtain acylindrical accessibility for actions on CAT(0) cube complexes and bounds on curves on surfaces.
-
Notes on Geometric Graph TheoryJ. Pach · 1990 · Discrete & Computational Geometry · cité 32 fois · Pas encore résumé
« Notes on Geometric Graph Theory » est un chapitre de notes consacré à la théorie géométrique des graphes.
Résumé scientifique
Note: Professor Pach's number: [092] Reference DCG-CHAPTER-2008-008 Record created on 2008-11-18, modified on 2017-05-12
Aller plus loin
Comment ces articles sont-ils trouvés ?
Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.
Mis à jour le 9 novembre 2026.