Quasi-planar graphs have a linear number of edges
From MaRDI portal
Publication:1375051
DOI10.1007/BF01196127zbMath0880.05050DBLPjournals/combinatorica/AgarwalAPPS97OpenAlexW2775046532WikidataQ57253828 ScholiaQ57253828MaRDI QIDQ1375051
Pankaj K. Agarwal, Boris Aronov, Richard Pollack, János Pach, Micha Sharir
Publication date: 5 January 1998
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01196127
Extremal problems in graph theory (05C35) Combinatorics in computer science (68R05) Connectivity (05C40)
Related Items (62)
The density of fan-planar graphs ⋮ Simplifying Non-Simple Fan-Planar Drawings ⋮ Geometric graphs with no self-intersecting path of length three ⋮ Recognizing and drawing IC-planar graphs ⋮ Drawing Graphs with Right Angle Crossings ⋮ Simplifying non-simple fan-planar drawings ⋮ Applications of the crossing number ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ On the maximum number of edges in quasi-planar graphs ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ Noncrossing Hamiltonian paths in geometric graphs ⋮ Coloring curves that cross a fixed curve ⋮ k-Quasi-Planar Graphs ⋮ A Linear Kernel for Planar Feedback Vertex Set ⋮ The family of fan-planar graphs ⋮ On neighbors in geometric permutations. ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ Quasiplanar graphs, string graphs, and the Erdős-Gallai problem ⋮ On the Size of Planarly Connected Crossing Graphs ⋮ On the Density of Non-simple 3-Planar Graphs ⋮ On the edge crossing properties of Euclidean minimum weight Laman graphs ⋮ New bounds on the maximum number of edges in \(k\)-quasi-planar graphs ⋮ On fan-crossing graphs ⋮ Efficient generation of different topological representations of graphs beyond-planarity ⋮ The QuaSEFE problem ⋮ 1-fan-bundle-planar drawings of graphs ⋮ Unnamed Item ⋮ Faster Algorithms for the Minimum Red-Blue-Purple Spanning Graph Problem ⋮ Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count ⋮ Gap-Planar Graphs ⋮ A linear-time algorithm for testing full outer-2-planarity ⋮ Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar ⋮ Applications of a New Separator Theorem for String Graphs ⋮ Unnamed Item ⋮ Two-Planar Graphs Are Quasiplanar ⋮ Drawing graphs with right angle crossings ⋮ Unnamed Item ⋮ On-line approach to off-line coloring problems on graphs with geometric representations ⋮ On RAC drawings of graphs with one bend per edge ⋮ Gap-planar graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ Planar point sets determine many pairwise crossing segments ⋮ Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs ⋮ Packing and covering balls in graphs excluding a minor ⋮ Covering nearly surface-embedded graphs with a fixed number of balls ⋮ The maximum number of edges in geometric graphs with pairwise virtually avoiding edges ⋮ An upper bound on the number of edges in an almost planar bipartite graph ⋮ On the maximum number of edges in topological graphs with no four pairwise crossing edges ⋮ Twenty years of progress of \(\mathrm{JCDCG}^3\) ⋮ Testing Full Outer-2-planarity in Linear Time ⋮ Extremal problems on triangle areas in two and three dimensions ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Beyond Planar Graphs: Introduction ⋮ Quasi-planar Graphs ⋮ Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs ⋮ Topological graphs with no large grids ⋮ 2-Layer k-Planar Graphs ⋮ Fan-planarity: properties and complexity ⋮ On the Number of Edges of Fan-Crossing Free Graphs
Cites Work
This page was built for publication: Quasi-planar graphs have a linear number of edges
