New bounds on the maximum number of edges in k-quasi-planar graphs

DOI10.1007/978-3-319-03841-4_9zbMATH Open1328.05056arXiv1309.0395OpenAlexW1959141466MaRDI QIDQ904085FDOQ904085

Authors: Andrew Suk, Bartosz Walczak 

Publication date: 15 January 2016

Published in: Computational Geometry, Graph Drawing (Search for Journal in Brave)

Abstract: 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(logn{)}^{O(logk)}$ edges. We improve this upper bound to $2^{alpha(n{)}^c}nlogn$, where $alpha(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(nlogn)$ edges. This improves the previously known upper bound of $2^{alpha(n{)}^c}nlogn$ obtained by Fox, Pach, and Suk.

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

Recommendations

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

zbMATH Keywords

topological graphs[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Tur%EF%BF%BD%EF%BF%BDn-type+problems&go=Go Tur��n-type problems]\(k\)-quasi-planar graphs

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)

Cites Work

• Research Problems in Discrete Geometry
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Applications of a New Separator Theorem for String Graphs
• Quasi-planar graphs have a linear number of edges
• The Number of Edges in $k$-Quasi-planar Graphs
• A decomposition theorem for partially ordered sets
• Title not available (Why is that?)
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• On geometric graphs with no \(k\) pairwise parallel edges
• A Turán-type theorem on chords of a convex polygon
• Colouring arcwise connected sets in the plane. I
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Applications of the crossing number
• Title not available (Why is that?)
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Coloring intersection graphs of arc-connected sets in the plane
• On the structure and composition of forbidden sequences, with geometric applications
• Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
• On bounding the chromatic number of L-graphs
• Outerstring graphs are χ-bounded
• Title not available (Why is that?)

Cited In (31)

• Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count
• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• The density of fan-planar graphs
• Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs
• Bounding sequence extremal functions with formations
• Crossing numbers of beyond-planar graphs
• Crossing numbers of beyond-planar graphs
• Quasi-planar Graphs
• Two-Planar Graphs Are Quasiplanar
• Bounds on parameters of minimally nonlinear patterns
• Title not available (Why is that?)
• A linear-time algorithm for testing full outer-2-planarity
• Edge-minimum saturated \(k\)-planar drawings
• On-line approach to off-line coloring problems on graphs with geometric representations
• Quantitative Restrictions on Crossing Patterns
• On the zone of a circle in an arrangement of lines
• 2-Layer k-Planar Graphs
• On the maximum number of edges in quasi-planar graphs
• Coloring curves that cross a fixed curve
• Outerstring Graphs are $\chi$-Bounded
• Covering nearly surface-embedded graphs with a fixed number of balls
• On the Size of Planarly Connected Crossing Graphs
• \(k\)-quasi-planar graphs
• Sequence saturation
• An annotated bibliography on 1-planarity
• Unavoidable patterns in complete simple topological graphs
• Nonplanar Graph Drawings with k Vertices per Face
• Computing and Combinatorics
• A relationship between generalized Davenport-Schinzel sequences and interval chains
• Unavoidable patterns in complete simple topological graphs
• The family of fan-planar graphs

This page was built for publication: New bounds on the maximum 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 Q904085)