The Maximum Number of Edges in Geometric Graphs with Pairwise Virtually Avoiding Edges

作者：Ackerman Eyal; Nitzan Noa^*; Pinchasi Rom

来源：Graphs and Combinatorics, 2014, 30(5): 1065-1072.

DOI：10.1007/s00373-013-1335-7

• Geometric graph
• Avoiding edges
• Discharging method
• Parallel edges

Let G be a geometric graph on n vertices that are not necessarily in general position. Assume that no line passing through one edge of G meets the relative interior of another edge. We show that in this case the number of edges in G is at most 2n-3.

• 出版日期2014-9