Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235592] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Aronov, B; Pach, J; Pollack, R; Sharir, M, Quasi-planar graphs have a linear number of edges, Combinatorica, vol. 17 no. 1 (1997), pp. 1-9
    (last updated on 2017/12/14)

    Abstract:
    A graph is called quasi-planar 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 quasi-planar 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 27708-0320