Large planar subgraphs in dense graphs

Research output: Contribution to journalArticle

19 Citations (Scopus)


We prove sufficient and essentially necessary conditions in terms of the minimum degree for a graph Z to contain planar subgraphs with many edges. For example, for all positive gamma every sufficiently large graph G with minimum degree at least (2/3 + gamma) vertical bar G vertical bar contains a triangulation as a sparming subgraph, whereas this need not be the case when the minimum degree is less than 2 vertical bar G vertical bar/3. (c) 2005 Elsevier Inc. All rights reserved..
Original languageEnglish
Pages (from-to)263-282
Number of pages20
JournalJournal of Combinatorial Theory. Series B
Publication statusPublished - 1 Nov 2005


  • extremal graph theory
  • planar subgraphs
  • regularity lemma


Dive into the research topics of 'Large planar subgraphs in dense graphs'. Together they form a unique fingerprint.

Cite this