Quasi-planar graphs have a linear number of edges
From MaRDI portal
Publication:1375051
DOI10.1007/BF01196127zbMath0880.05050OpenAlexW2775046532WikidataQ57253828 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
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
