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

DOI10.1016/j.comgeo.2015.06.001zbMath1328.05056arXiv1309.0395OpenAlexW1959141466MaRDI QIDQ904085

Bartosz Walczak, Andrew Suk

Publication date: 15 January 2016

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

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

zbMATH Keywords

topological graphsTurán-type problems\(k\)-quasi-planar graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

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

Cites Work

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

This page was built for publication: New bounds on the maximum number of edges in \(k\)-quasi-planar graphs