The number of edges in k-quasi-planar graphs

DOI10.1137/110858586zbMATH Open1268.05051arXiv1112.2361OpenAlexW2072233942MaRDI QIDQ5300510FDOQ5300510

Andrew Suk, János Pach, Jacob Fox

Publication date: 27 June 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A graph drawn in the plane is called k-quasi-planar if it does not contain k pairwise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best known upper bound is n(log n)^{O(log k)}. In the present note, we improve this bound to (nlog n)2^{alpha^{c_k}(n)} in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here alpha(n) denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for k-quasi-planar graphs in which every edge is drawn as an x-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most 2^{ck^6}nlog n.

Full work available at URL: https://arxiv.org/abs/1112.2361

Recommendations

• New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
• New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
• \(k\)-quasi-planar graphs
• Quasi-planar graphs have a linear number of edges
• On the maximum number of edges in quasi-planar graphs

zbMATH Keywords

topological graphsquasi-planar graphsTuran-type problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Erd?s problems and related topics of discrete geometry (52C10)

Cited In (43)

• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• Beyond Planar Graphs: Introduction
• The density of fan-planar graphs
• The number of crossings in multigraphs with no empty lens
• Beyond Outerplanarity
• Min-\(k\)-planar drawings of graphs
• On the number of edges of quadrilateral-free graphs
• Edges and Kuratowski Subgraphs of Non-Planar Graphs
• Bounding sequence extremal functions with formations
• Quasi-planar Graphs
• Two-Planar Graphs Are Quasiplanar
• New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
• Bounds on parameters of minimally nonlinear patterns
• Title not available (Why is that?)
• A linear-time algorithm for testing full outer-2-planarity
• Recognizing and drawing IC-planar graphs
• Testing Full Outer-2-planarity in Linear Time
• Constructing sparse Davenport-Schinzel sequences
• Three Generalizations of Davenport--Schinzel Sequences
• On the zone of a circle in an arrangement of lines
• On the zone of a circle in an arrangement of lines
• 2-Layer k-Planar Graphs
• Min-\(k\)-planar drawings of graphs
• Coloring curves that cross a fixed curve
• Outerstring Graphs are $\chi$-Bounded
• Covering nearly surface-embedded graphs with a fixed number of balls
• Title not available (Why is that?)
• Gap-Planar Graphs
• Gap-planar graphs
• On RAC drawings of graphs with one bend per edge
• On the edge crossing properties of Euclidean minimum weight Laman graphs
• Fan-planarity: properties and complexity
• Sequence saturation
• On quasi-planar graphs: clique-width and logical description
• An annotated bibliography on 1-planarity
• On RAC drawings of graphs with one bend per edge
• On the Number of Edges of Fan-Crossing Free Graphs
• On convex geometric graphs with no \(k+1\) pairwise disjoint edges
• Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
• A relationship between generalized Davenport-Schinzel sequences and interval chains
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• The family of fan-planar graphs
• The QuaSEFE problem

This page was built for publication: The number of edges in \(k\)-quasi-planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300510)