On the Number of Edges of Fan-Crossing Free Graphs

DOI10.1007/978-3-642-45030-3_16zbMath1329.05079arXiv1311.1976OpenAlexW2615925897MaRDI QIDQ2872081

Heuna Kim, Hyo-Sil Kim, Otfried Schwarzkopf, Sariel Har-Peled

Publication date: 14 January 2014

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

graph theorycrossing numberplanar graphgraph drawingextremal graph\(K\)-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) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (27)

The density of fan-planar graphs ⋮ Simplifying Non-Simple Fan-Planar Drawings ⋮ Simplifying non-simple fan-planar drawings ⋮ Recognizing and embedding simple optimal 2-planar graphs ⋮ On fan-crossing and fan-crossing free graphs ⋮ Crossing Numbers of Beyond-Planar Graphs Revisited ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ Straight-line drawings of 1-planar graphs ⋮ The family of fan-planar graphs ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ On the Density of Non-simple 3-Planar Graphs ⋮ On fan-crossing graphs ⋮ Efficient generation of different topological representations of graphs beyond-planarity ⋮ 1-fan-bundle-planar drawings of graphs ⋮ Unnamed Item ⋮ Gap-Planar Graphs ⋮ A linear-time algorithm for testing full outer-2-planarity ⋮ Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity ⋮ Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar ⋮ On RAC drawings of graphs with one bend per edge ⋮ Gap-planar graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ Testing Full Outer-2-planarity in Linear Time ⋮ Beyond Planar Graphs: Introduction ⋮ Right Angle Crossing Drawings of Graphs ⋮ Fan-planarity: properties and complexity

Cites Work

• Drawing graphs with right angle crossings
• Improving the crossing lemma by finding more crossings in sparse graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Graphs drawn with few crossings per edge
• Quasi-planar graphs have a linear number of edges
• Applications of the crossing number
• Density of straight-line 1-planar graph drawings
• Right angle crossing graphs and 1-planarity
• Algorithms for graphs embeddable with few crossings per edge
• Topological graphs with no large grids
• Fáry’s Theorem for 1-Planar Graphs
• The Straight-Line RAC Drawing Problem is NP-Hard
• The Number of Edges in $k$-Quasi-planar Graphs
• Discrete and Computational Geometry

This page was built for publication: On the Number of Edges of Fan-Crossing Free Graphs