The Number of Edges in $k$-Quasi-planar Graphs
From MaRDI portal
Publication:5300510
DOI10.1137/110858586zbMath1268.05051arXiv1112.2361OpenAlexW2072233942MaRDI QIDQ5300510
Andrew Suk, János Pach, Jacob Fox
Publication date: 27 June 2013
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1112.2361
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) Erd?s problems and related topics of discrete geometry (52C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (38)
The density of fan-planar graphs ⋮ Recognizing and drawing IC-planar graphs ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ On quasi-planar graphs: clique-width and logical description ⋮ An annotated bibliography on 1-planarity ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ Constructing sparse Davenport-Schinzel sequences ⋮ 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 ⋮ On the edge crossing properties of Euclidean minimum weight Laman graphs ⋮ New bounds on the maximum number of edges in \(k\)-quasi-planar graphs ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ The QuaSEFE problem ⋮ Unnamed Item ⋮ On the zone of a circle in an arrangement of lines ⋮ On the zone of a circle in an arrangement of lines ⋮ Gap-Planar Graphs ⋮ Beyond Outerplanarity ⋮ A linear-time algorithm for testing full outer-2-planarity ⋮ On convex geometric graphs with no \(k+1\) pairwise disjoint edges ⋮ Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar ⋮ Two-Planar Graphs Are Quasiplanar ⋮ Unnamed Item ⋮ On RAC drawings of graphs with one bend per edge ⋮ Gap-planar graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ A relationship between generalized Davenport-Schinzel sequences and interval chains ⋮ Covering nearly surface-embedded graphs with a fixed number of balls ⋮ Testing Full Outer-2-planarity in Linear Time ⋮ The number of crossings in multigraphs with no empty lens ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Beyond Planar Graphs: Introduction ⋮ Quasi-planar Graphs ⋮ 2-Layer k-Planar Graphs ⋮ Fan-planarity: properties and complexity ⋮ On the Number of Edges of Fan-Crossing Free Graphs
This page was built for publication: The Number of Edges in $k$-Quasi-planar Graphs
