On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing Edges |
| |
| Authors: | Eyal Ackerman |
| |
| Institution: | (1) Computer Science Dept., Technion—Israel Institute of Technology, Haifa, 32000, Israel |
| |
| Abstract: | A topological graph is called k
-quasi-planar if it does not contain k pairwise crossing edges. It is conjectured that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). We provide an affirmative answer to the case k=4. |
| |
| Keywords: | Geometric graphs Topological graphs Discharging method Quasi-planar graphs |
| 本文献已被 SpringerLink 等数据库收录！ |
