On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing Edges

被引：47

作者：

Ackerman, Eyal ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2009年 / 41卷 / 03期

关键词：

Geometric graphs; Topological graphs; Discharging method; Quasi-planar graphs;

D O I：

10.1007/s00454-009-9143-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：365 / 375

页数：11