ISSN:
1432-0541
Keywords:
Crossing number
;
Geometric graph
;
Bisection width
;
Triangulation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract LetG be a graph ofn vertices that can be drawn in the plane by straight-line segments so that nok+1 of them are pairwise crossing. We show thatG has at mostc k nlog2k−2 n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erdós, Kupitz, Perles, and others. We also construct two point sets {p 1,⋯,p n }, {q 1,⋯,q n } in the plane such that any piecewise linear one-to-one mappingf∶R 2→R 2 withf(pi)=qi (1≤i≤n) is composed of at least Ω(n 2) linear pieces. It follows from a recent result of Souvaine and Wenger that this bound is asymptotically tight. Both proofs are based on a relation between the crossing number and the bisection width of a graph.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02086610
Permalink
