Geometric Graphs and Arrangements

Stefan Felsner

Corrections Page

  1. p8 (Definition of the orders $\prec_i$): Replace $e\prec_i e'$ by $e'\prec_i e$ in the four instances.

  2. p11 (Lemma 1.15): $RS(G)$ instead of $|RS(G)|$.

    Note: Rom Pinchasi has a new and very nice proof for Theorem 1.13.
    The idea is to consider the convex set Ki spanned by the points with label i on the circle C. With Lemma 1.15 it follows that the Ki are pairwise disjoint. Take two copies C1, C2 of the disk bounded by C and glue them along the cycles such that points p on C1 and q on C2 get matched whenever p and q are the different intersection points of a line le supporting an edge e. Blow air between the disks to make it a sphere. The intersection graph of the sets Ki and K'i on the sphere is planar and bipartite with 2n vertices. Hence, it has at most 2(2n) -4 edges. These edges are a double count of the edges of G.

  3. p15 Note: A simple proof for the linearity of edges of a quasi-planar graph was found by Eyal Ackerman and Gabor Tardos.

  4. p44 (last line): The upper bound of the sum ought to be $\lfloor\frac{m}{r}\rfloor -1$.

  5. p46 (between Thm 3.5 and proof): Let $G_3=G$ and for $i=2,1,0$ define a subgraph $G_i$ of $G_{i+1}$ by removing edges which have $i+1$ crossings until there are no such edges left. With this modified definition of $G_i$ it is true that an edge from $E(G_{i+1}) \ E(G_i)$ has $i+1$ crossings with edges from $G_i$.

  6. p48 (Figure 3.4): The edges added in the outer faces are missing. corrected figure

  7. p48 The constant 3.3 in Theorem 3.6 can be replaced by 2.7, in the proof replace m^2 > cr(G) by m^2/2 > cr(G).

  8. p50 (line 3): $m(G') \leq 6n$.

  9. p51 (line 9): The new constant is 0.031.

  10. p51 Note: A simple proof Tutte's result stating that graphs with odd-crossing number zero are planar was obtained by Michael J. Pelsmajer, Marcus Schaefer and Daniel Stefankovic: Removing Even Crossings.

  11. p59 (two lines before Fact 1.) $(k+d)$-element subsets
  12. p59 (proof of Fact 1.) $s^k = \sum_j \binom{j}{k}\hh_j$

  13. p72 (bottom): The statement Every arrangement ......... a point contained in exactly two of the lines. is stronger than the dual of Proposition 5.2. Upon dualization an ordinary line may end up as a pair of parallel lines.
    Still the given statement is correct and admits a proof via a distance argument in the spirit of Kelly's proof.
    This has been pointed out by Jonathan Lenchner. He is author of note discussing the dual of Sylvester's Theorem [pdf].

  14. p72 (line -6) $px$ for $T_2$ and $qx$ for $T_1$

  15. p80 (line -3) has at least $\lceil 2n/3 \rceil$ triangles

  16. p97 (last line) lines to $\BB(n)$, i.e., $B_n \leq |\BB(n)|$.

  17. p 110(line 9) define $\tau_t:\binom{[n]}{r-1}\to\{+,-\}$ by

  18. p 137-138 Note: There is a simpler proof for the implication $(3\rightarrow1)$ from Theorem 8.9. The new proof widely follow the approach taken by A.Frank and L.Szegö in [93]. New proof

Februar 2006