Geometric Graphs and Arrangements
Stefan Felsner
Corrections Page
- p8 (Definition of the orders $\prec_i$): Replace $e\prec_i e'$ by $e'\prec_i e$
in the four instances.
- 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.
Q.E.D.
- p15 Note: A simple proof for the linearity of edges of a quasi-planar graph
was found by Eyal Ackerman and
Gabor Tardos.
- p44 (last line): The upper bound of the sum ought to be $\lfloor\frac{m}{r}\rfloor -1$.
- 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$.
- p48 (Figure 3.4): The edges added in the outer faces are missing.
corrected figure
- 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).
- p50 (line 3): $m(G') \leq 6n$.
- p51 (line 9): The new constant is 0.031.
- 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.
- p59 (two lines before Fact 1.) $(k+d)$-element subsets
- p59 (proof of Fact 1.) $s^k = \sum_j \binom{j}{k}\hh_j$
- 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].
- p72 (line -6)
$px$ for $T_2$ and $qx$ for $T_1$
- p80 (line -3)
has at least $\lceil 2n/3 \rceil$ triangles
- p97 (last line)
lines to $\BB(n)$, i.e., $B_n \leq |\BB(n)|$.
- p 110(line 9)
define $\tau_t:\binom{[n]}{r-1}\to\{+,-\}$ by
- 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