Abstract
A graph is calledquasi-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 withn vertices isO(n).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
V. Capoyleas andJ. Pach: A Turán-type theorem on chords of a convex polygon,J. Combin. Theory, Ser. B,56 (1992), 9–15.
M. Golumbic:Algorithmic Graph Theory, Academic Press, New York, 1980.
A. Gyárfás: On the chromatic number of multiple interval graphs and overlap graphs,Discrete Math.,55 (1985), 161–166.
A. Gyárfás andJ. Lehel: Covering and coloring problems for relatives of intervals,Discrete Math.,55 (1985), 167–180.
A. V. Kostochka: On upper bounds for the chromatic number of graphs, in:Modeli i metody optimizacii, Tom 10, Akademiya Nauk SSSR, Sibirskoe Otdelenie, 1988, 204–226.
J. Pach andP. K. Agarwal:Combinatorial Geometry, Wiley-Interscience, New York, 1995.
J. Pach, F. Sharokhi, andM. Szegedy: Applications of the crossing number,Proc. 10th Annual ACM Symp. on Computational Geometry (1994), pp. 198–202. Also to appear inalgorithmica.
Author information
Authors and Affiliations
Additional information
Work on this paper by Pankaj K. Agarwal, Boris Aronov and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work on this paper by Pankaj K. Agarwal has also been supported by NSF Grant CCR-93-01259, by an Army Research Office MURI grant DAAH04-96-1-0013, by an NYI award, and by matching funds from Xerox Corporation. Work on this paper by Boris Aronov has also been supported by NSF Grant CCR-92-11541 and by a Sloan Research Fellowship. Work on this paper by János Pach, Richard Pollack, and Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-94-24398. Work by János Pach was also supported by Grant OTKA-4269 and by a CUNY Research Award. Work by Richard Pollack was also supported by NSF Grants CCR-94-02640 and DMS-94-00293. Work by Micha Sharir was also supported by NSF Grant CCR-93-11127, by a Max-Planck Research Award, and by grants from the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Part of the work on this paper was done during the participation of the first four authors in the Special Semester on Computational and Combinatorial Geometry organized by the Mathematical Research Institute of Tel Aviv University, Spring 1995.