Quasi-planar graphs have a linear number of edges

Pankaj K. Agarwal, Boris Aronov, János Pach, Richard Pollack, Micha Sharir

Type: Book-Chapter

Publication Date: 1996-01-01

Citations: 23

DOI: https://doi.org/10.1007/bfb0021784

View

Locations

Lecture notes in computer science - View

Similar Works

Action	Title	Year	Authors
+	Quasi-planar graphs have a linear number of edges	1997	Pankaj K. Agarwal Boris Aronov J�nos Pach Richard Pollack Micha Sharir
+	Two-Planar Graphs Are Quasiplanar	2017	Michael M. Hoffmann Csaba D. Tóth
+	Two-Planar Graphs Are Quasiplanar	2017	Michael M. Hoffmann Csaba D. Tóth
+	On the size of planarly connected crossing graphs	2015	Eyal Ackerman Balázs Keszegh Máté Vizer
+	On the size of planarly connected crossing graphs	2015	Eyal Ackerman Balázs Keszegh Máté Vizer
+	On the size of planarly connected crossing graphs	2017	Eyal Ackerman Balázs Keszegh Máté Vizer
+	On the Relationship between $k$-Planar and $k$-Quasi Planar Graphs	2017	Patrizio Angelini Michael A. Bekos Franz J. Brandenburg Giordano Da Lozzo Giuseppe Di Battista Walter Didimo Giuseppe Liotta Fabrizio Montecchiani Ignaz Rutter
+	The Number of Edges in k-Quasi-planar Graphs	2013	Jacob Fox János Pach Andrew Suk
+	The number of edges in k-quasi-planar graphs	2011	Jacob Fox János Pach Andrew Suk
+	The number of edges in k-quasi-planar graphs	2011	Jacob Fox János Pach Andrew Suk
+ PDF Chat	The Number of Edges in $k$-Quasi-planar Graphs	2013	Jacob Fox János Pach Andrew Suk
+	$k$-quasi planar graphs	2011	Andrew Suk
+	$k$-quasi planar graphs	2011	Andrew Suk
+	New bounds on the maximum number of edges in k-quasi-planar graphs	2015	Andrew Suk Bartosz Walczak
+	Thrackles: An Improved Upper Bound	2017	Radoslav Fulek János Pach
+	Thrackles: An Improved Upper Bound	2017	Radoslav Fulek János Pach
+	Crossing Numbers of Beyond-Planar Graphs	2019	Markus Chimani Philipp Kindermann Fabrizio Montecchiani Pável Valtr
+	Crossing Numbers of Beyond-Planar Graphs	2019	Markus Chimani Philipp Kindermann Fabrizio Montecchiani Pável Valtr
+ PDF Chat	Non-crossing Shortest Paths Lengths in Planar Graphs in Linear Time	2023	Lorenzo Balzotti Paolo Giulio Franciosa
+ PDF Chat	On the Pseudolinear Crossing Number	2016	César Hernández-Vélez Jesús Leaños Gelasio Salazar

Cited by (14)

Action	Title	Year	Authors
+ PDF Chat	Extremal problems on triangle areas in two and three dimensions	2009	Adrian Dumitrescu Micha Sharir Csaba D. Tóth
+ PDF Chat	Graph drawing with no k pairwise crossing edges	1997	Pável Valtr
+ PDF Chat	Covering Planar Graphs with a Fixed Number of Balls	2007	Victor Chepoi Bertrand Estellon Yann Vaxès
+ PDF Chat	Geometric Graphs with No Three Disjoint Edges	2005	Jakub Černý
+	On disjoint crossing families in geometric graphs	2010	Radoslav Fulek Andrew Suk
+	$k$-quasi planar graphs	2011	Andrew Suk
+ PDF Chat	An Upper Bound on the Number of Edges in an Almost Planar Bipartite Graph	2014	D. V. Karpov
+	New bounds on the maximum number of edges in k-quasi-planar graphs	2015	Andrew Suk Bartosz Walczak
+	Recognizing and drawing IC-planar graphs	2016	Franz J. Brandenburg Walter Didimo William Evans Philipp Kindermann Giuseppe Liotta Fabrizio Montecchiani
+	Fan-planarity: Properties and complexity	2015	Carla Binucci Emilio Di Giacomo Walter Didimo Fabrizio Montecchiani Maurizio Patrignani Antonios Symvonis Ioannis G. Tollis
+ PDF Chat	Simple k-planar graphs are simple (k + 1)-quasiplanar	2019	Patrizio Angelini Michael A. Bekos Franz J. Brandenburg Giordano Da Lozzo Giuseppe Di Battista Walter Didimo Michael M. Hoffmann Giuseppe Liotta Fabrizio Montecchiani Ignaz Rutter
+ PDF Chat	Min-$k$-planar Drawings of Graphs	2024	Carla Binucci Aaron Büngener Giuseppe Di Battista Walter Didimo Vida Dujmović Seok-Hee Hong Michael Kaufmann Giuseppe Liotta Pat Morin Alessandra Tappini
+ PDF Chat	Graph Drawing and Network Visualization	2019	Daniel Archambault Csaba D. Tóth
+ PDF Chat	The Density of Fan-Planar Graphs	2022	Michael Kaufmann Torsten Ueckerdt

Citing (5)

Action	Title	Year	Authors
+	Covering and coloring problems for relatives of intervals	1985	András Gyárfás Jenö Lehel
+	Applications of the crossing number	1994	János Pach Farhad Shahrokhi Márió Szegedy
+	A turán-type theorem on chords of a convex polygon	1992	Vasilis Capoyleas János Pach
+	On the chromatic number of multiple interval graphs and overlap graphs	1985	András Gyárfás
+	Combinatorial Geometry	1995	János Pach Pankaj K. Agarwal