The number of edges in k-quasi-planar graphs
From MaRDI portal
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)
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.
Recommendations
Cited in
(44)- Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
- The density of fan-planar graphs
- Three generalizations of Davenport-Schinzel sequences
- The number of crossings in multigraphs with no empty lens
- Min-\(k\)-planar drawings of graphs
- On the number of edges of quadrilateral-free graphs
- Bounding sequence extremal functions with formations
- Edges and Kuratowski Subgraphs of Non-Planar Graphs
- Quasi-planar Graphs
- Two-Planar Graphs Are Quasiplanar
- Bounds on parameters of minimally nonlinear patterns
- A linear-time algorithm for testing full outer-2-planarity
- scientific article; zbMATH DE number 7673608 (Why is no real title available?)
- Testing Full Outer-2-planarity in Linear Time
- Constructing sparse Davenport-Schinzel sequences
- On the maximum number of edges in quasi-planar graphs
- 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
- Beyond planar graphs: introduction
- Coloring curves that cross a fixed curve
- Min-k-planar drawings of graphs
- Covering nearly surface-embedded graphs with a fixed number of balls
- Gap-Planar Graphs
- Quasi-planar graphs have a linear number of edges
- Beyond outerplanarity
- 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
- k-quasi-planar graphs
- On quasi-planar graphs: clique-width and logical description
- Sequence saturation
- An annotated bibliography on 1-planarity
- On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
- On RAC drawings of graphs with one bend per edge
- On convex geometric graphs with no \(k+1\) pairwise disjoint edges
- Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs
- Outerstring graphs are -bounded
- A relationship between generalized Davenport-Schinzel sequences and interval chains
- On the recognition of fan-planar and maximal outer-fan-planar graphs
- Beyond-planarity: Turán-type results for non-planar bipartite 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)
