Math @ Duke

Publications [#235592] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Pach, J; Pollack, R; Sharir, M, Quasiplanar graphs have a linear number of edges,
Combinatorica, vol. 17 no. 1
(1997),
pp. 19
(last updated on 2018/07/22)
Abstract: A graph is called quasiplanar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasiplanar graph with n vertices is O(n).


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

