\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1}{20(3)}{2013} \usepackage{amsmath,amssymb,amsthm} \usepackage{tikz} \usetikzlibrary{shapes} \usepackage[colorlinks=true,bookmarks,linkcolor=black,urlcolor=blue,citecolor=black]{hyperref} % \renewcommand{\baselinestretch}{1.8} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} %%%% LISTS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\setlist{itemsep=1pt,parsep=0pt,topsep=2pt,partopsep=0pt} %\setenumerate{leftmargin=*} %%% LABELS %\def\itm#1{\rm ({#1})} %\def\itmit#1{\itm{\it #1\,}} %\def\rom{\itm{\roman{*}}} %\def\abc{\itm{\alph{*}}} %\def\arab{\itm{\arabic{*}}} %\def\irom{\itmit{\roman{*}}} %\def\iabc{\itmit{\alph{*}}} %\def\iarab{\itmit{\arabic{*}}} %\def\endofFact{\hfill\scalebox{.6}{$\Box$}} %%%% DEFLETS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \let\version\today \let\subset\subseteq \let\eps\varepsilon \let\phi\varphi \let\rho\varrho %\def\dcup{\dot\cup} \def\bound{\partial} %\def\subsc#1{\textsc{\MakeTextLowercase{#1}}} % needs package textcase %%%% THEOREMS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newtheorem{theorem}{Theorem}%[section] \newtheorem{lemma}[theorem] {Lemma} \newtheorem{corollary}[theorem] {Corollary} \newtheorem{conjecture}[theorem] {Conjecture} \newtheorem{proposition}[theorem] {Proposition} \newtheorem{claim}[theorem] {Claim} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem] {Observation} \newtheorem{definition}[theorem] {Definition} \theoremstyle{remark} \newtheorem{remark}[theorem] {Remark} %%%% COMMANDS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\comment}[1]{\marginpar{\baselineskip=.6\baselineskip \textcolor{red}{\sffamily\footnotesize #1}}} % \newcommand{\comment}[1]{} % explanations above <,>,=,\le,\ge \newcommand{\By}[2]{\overset{\mbox{\tiny{#1}}}{#2}} \newcommand{\ByRef}[2]{ \By{\eqref{#1}}{#2} } \newcommand{\eqBy}[1]{ \By{#1}{=} } \newcommand{\lBy}[1]{ \By{#1}{<} } \newcommand{\gBy}[1]{ \By{#1}{>} } \newcommand{\leBy}[1]{ \By{#1}{\le} } \newcommand{\geBy}[1]{ \By{#1}{\ge} } \newcommand{\eqByRef}[1]{ \ByRef{#1}{=} } \newcommand{\lByRef}[1]{ \ByRef{#1}{<} } \newcommand{\gByRef}[1]{ \ByRef{#1}{>} } \newcommand{\leByRef}[1]{ \ByRef{#1}{\le} } \newcommand{\geByRef}[1]{ \ByRef{#1}{\ge} } \newcommand{\REALS}{\mathbb{R}} \newcommand{\RATS}{\mathbb{Q}} \newcommand{\NATS}{\mathbb{N}} \newcommand{\bigO}{\mathcal{O}} %\newcommand{\BAR}[1]{\overline{#1}} %\newcommand{\bw}{\operatorname{bw}} % bandwidth %\newcommand{\chicr}{\chi_{\rm cr}} % chrit. chrom. number \DeclareMathOperator{\intr}{int} % interior \DeclareMathOperator{\dist}{dist} % distance in a graph \DeclareMathOperator{\CTF}{CTF} % connected triangle factor \DeclareMathOperator{\sqp}{sp} % square-path \DeclareMathOperator{\sqc}{sc} % square-cycle \DeclareMathOperator{\pl}{pl} % planarity \DeclareMathOperator{\dcup}{\ensuremath{\mathaccent\cdot \cup}} % disjoint union \newcommand{\rp}{r_p} % r-path \newcommand{\rc}{r_c} % r-cycle % \newcommand{\overrightharp}[1]{{\overrightarrow{#1}} % \newcommand{\overrightharp}[1]{\smash{\overset{\rightharpoonup}{\smash{#1}\vphantom{a}}}} % \newcommand{\overrightharp}[1]{\smash{\overset{\scalebox{1}[1.5]{$\rightharpoonup$}}{\smash{#1}\vphantom{a}}}} \newcommand{\overrightharp}[1]{{\overset{\scalebox{1.8}[.7]{\!\!\!\raisebox{-.5pt}{$\rightharpoonup$}}}{\smash{#1}\vphantom{a}}}} \newcommand{\EMAIL}[1]{ \textit{E-mail}: \texttt{#1} } \newcommand{\oldqed}{} \newenvironment{factproof}[1][Proof]{ \renewcommand{\oldqed}{\qedsymbol} \renewcommand{\qedsymbol}{\endofFact} \begin{proof}[#1] }{ \end{proof} \renewcommand{\qedsymbol}{\oldqed} } %macros for comments %\def\JS#1{\marginpar{{\small {\bf JS:} #1}}} %\def\AW#1{\marginpar{{\small {\bf AW:} #1}}} %%%% PREAMBLE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf Maximum planar subgraphs in dense graphs} \author{Peter Allen\\ \small Department of Mathematics\\[-0.8ex] \small London School of Economics\\[-0.8ex] \small Houghton Street, London WC2A 2AE, United Kingdom\\ \small\tt p.d.allen@lse.ac.uk\\ \and Jozef Skokan\\ \small Department of Mathematics\\[-0.8ex] \small London School of Economics\\[-0.8ex] \small Houghton Street, London WC2A 2AE, United Kingdom\\ \small and\\ \small Department of Mathematics\\[-0.8ex] \small University of Illinois\\[-0.8ex] \small 1409 W. Green Street, Urbana, IL 61801, United States\\ \small\tt j.skokan@lse.ac.uk\\ \and Andreas W\"urfl\\ \small Zentrum Mathematik\\[-0.8ex] \small Technische Universität M\"unchen\\[-0.8ex] \small Boltzmann\-strasse~3 D-85748, Garching bei M\"unchen, Germany\\ \small\tt wuerfl@ma.tum.de } \date{\dateline{Jan 8, 2013}{June 28, 2013}{July 19, 2013}\\ \small Mathematics Subject Classifications: 05C35, 05C10} %%%% DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle \begin{abstract} K\"uhn, Osthus and Taraz showed that for each $\gamma>0$ there exists $C$ such that any $n$-vertex graph with minimum degree $\gamma n$ contains a planar subgraph with at least $2n-C$ edges. We find the optimum value of $C$ for all $\gamma< 1/2$ and sufficiently large $n$. \end{abstract} \section{Introduction} %\label{sec:Intro} %\thispagestyle{empty} A way to reformulate typical questions in extremal graph theory is the following. Given a property $\mathcal{P}$ and an edge density (or minimum vertex degree, etc.), what is the `largest' member of $\mathcal{P}$ which must be contained in an $n$-vertex graph $G$ with the given density? For many problems in extremal graph theory, the property $\mathcal{P}$ is somewhat trivial (for example, in Tur\'an's theorem, $\mathcal{P}$ is the set of cliques). However this is not always the case: for example, in the Erd\H{o}s-Stone~\cite{ErdSto46} theorem, $\mathcal{P}$ is the set of complete $r$-partite graphs, and the problem of determining the `largest' complete $r$-partite subgraph remains active, with most recently results and generalisations due to Nikiforov \cite{Niki11}. In 2005, K\"uhn, Osthus and Taraz~\cite{KuOsTa05} suggested the study of the property $\mathcal{P}$ consisting of all planar graphs, which, while well-studied in other parts of graph theory, have received relatively little attention from extremal graph theorists. \smallskip A plane graph is a drawing of a graph in the plane with no crossing edges. A graph is called planar if it has a plane graph drawing. The planarity of a graph $G$ is defined as the maximum number of edges in a planar subgraph of $G$. We denote the planarity of $G$ by $\pl(G)$. K\"uhn, Osthus and Taraz~\cite{KuOsTa05} investigated the connection between the minimum degree $\delta(G)$ and planarity $\pl(G)$ of a graph $G$ by studying the parameter $$ \pl(n,d):=\min\{\pl(G): |G|=n, \delta(G)\ge d\}. $$ Among other results they proved the following theorem. \begin{theorem} \label{thm:KOTtriang} For each $\gamma>0$ there exists a constant $n_\gamma$ such that $\pl\big(n, (2/3+\gamma) n\big) = 3n-6$ for every integer $n\ge n_\gamma$. \end{theorem} This was later improved by K\"uhn and Osthus~\cite{KuhOst05} to the following result with the optimal bound on the minimum degree. \begin{theorem} \label{thm:KOtriang} There exists $n_2$ such that $\pl(n, 2n/3) = 3n-6$ for every integer $n\ge n_2$. \end{theorem} More recently, Cooley, {\L}uczak, Taraz and W\"urfl~\cite{CLTW12} showed the following threshold behaviour of $\pl(n,d)$ at minimum degree $d=n/2$. \begin{theorem} \label{thm:CLTWjump} For every $\mu>0$ there exists $n_\mu$ such that, for every $n\ge n_\mu$, we have that \begin{align*} \pl\big(n, \lceil n/2\rceil\big) &\ge (2.25-\mu)n & &\text{ for $n$ odd,}\\ \intertext{and} \pl(n,n/2+1) &\ge (2.5-\mu)n & &\text{ for $n$ even.} \end{align*} \end{theorem} This indeed constitutes a threshold behaviour since $\pl(n,\lfloor n/2\rfloor)\le 2n-4$ for all integers $n$ as one can see from the class of complete bipartite graphs. For smaller values of $d$ one does not observe such rapid changes in the planarity. Indeed, K\"uhn, Osthus and Taraz~\cite{KuOsTa05} showed that $\pl(n,d)$ varies only by a constant term for the whole range of $d=\gamma n$ with $\gamma \in (0,1/2)$. %\AW{Is this too much results of other people? If you think so, I suggest to omit Thm~\ref{thm:CLTWjump}.} \begin{theorem}\label{thm:KOTquad} For each $\gamma>0$ there is $C=C(\gamma)$ such that $\pl(n,\gamma n) \ge 2n - C$ for every integer $n$. \end{theorem} For $\gamma<1/2$ this is optimal up to the value of the constant $C$. For $\gamma\ge 1/2$ the above statement trivially holds: a Hamilton cycle with chords from one vertex on the inner face and from another vertex on the outer face proves that every $n$-vertex graph with minimum degree at least $n/2$ has a planar subgraph with $2n-4$ edges. So it is natural to ask whether there are values $\gamma<1/2$ such that $C(\gamma)=4$. We answer this in the affirmative as we determine the optimal value of $C(\gamma)$ for all $0<\gamma<1/2$. \begin{theorem}\label{thm:main} For every $\gamma\in(0,1/2)$ there exists $n_\gamma$ such that $\pl(n,\gamma n) = 2n-4k$ for every $n\ge n_\gamma$, where $k\in\NATS$ is the unique integer such that $k\le 1/(2\gamma)< k+1$. Hence, $C(\gamma)=4\lfloor1/(2\gamma)\rfloor$ for $n\ge n_\gamma$. \end{theorem} Note that the constants are best possible for the given minimum degree condition: the graph consisting of $k$ disjoint copies of $K_{t,t}$ has $2kt$ vertices, is $t$-regular, and has no planar subgraph with more than $4kt-4k$ edges because $K_{t,t}$ has no planar subgraph with more than $4t-4$ edges. \section{Tools and lemmas} Our main tools in the proof are variants of the Regularity Lemma~\cite{Szem78} and the Blow-up Lemma~\cite{KSS97}. In order to formulate the versions that we will use, we first introduce some terminology. Let $G=(V, E)$ be a graph and let $\eps,d\in(0,1]$. For disjoint nonempty sets $U,W\subset V$, we denote by $e(U, W)$ the number of edges between $U$ and $W$, and define the \emph{density} of the pair $(U,W)$ as $d(U,W):=e(U,W)/|U||W|$. A pair $(U,W)$ is \emph{$\eps$-regular} if $$|d(U',W')-d(U,W)|\le\eps$$ for all $U'\subset U$ and $W'\subset W$ with $|U'|\ge\eps|U|$ and $|W'|\ge\eps|W|$. If the pair $(U,W)$ is $\eps$-regular and has density at least $d$, then we say that $(U,W)$ is \emph{$(\eps,d)$-regular}. An \emph{$\eps$-regular partition} of~$G=(V, E)$ is a partition $V_0\dcup V_1\dcup\dots\dcup V_r$ of $V$ with $|V_0|\le\eps |V|$, $|V_i|=|V_j|$ for all $i,j\in[r]:=\{1,\ldots,r\}$, and such that, for all but at most $\eps r^2$ pairs $(i,j)\in[r]^2$, the pair $(V_i,V_j)$ is $\eps$-regular. We say that an $\eps$-regular partition $V_0\dcup V_1\dcup\dots\dcup V_r$ of a graph $G$ is an \emph{$(\eps,d)$-regular partition} if the following is true. For every $i\in [r]$ and every vertex $v\in V_i$, there are at most $(\eps+d)n$ edges incident to $v$ which are not contained in $(\eps,d)$-regular pairs of the partition. Given an $(\eps,d)$-regular partition $V_0\dcup V_1\dcup\dots\dcup V_r$ of a graph $G$, we define a graph $R$, called the \emph{reduced graph} of the partition of $G$, where $R=(V(R),E(R))$ has $V(R)=\{V_1,\ldots,V_r\}$ and $V_iV_j\in E(R)$ whenever $(V_i,V_j)$ is an $(\eps,d)$-regular pair. We will usually omit the partition, and simply say that $G$ has \emph{$(\eps,d)$-reduced graph}~$R$. We call the partition classes $V_i$ with $i\in[r]$ \emph{clusters} of $G$. Observe that our definition of the reduced graph~$R$ implies that, for $T\subset V(R)$, we can, for example, refer to the set $\bigcup T$, which is a subset of $V(G)$. In our proof, we require the minimum degree form of the Regularity Lemma. \begin{lemma}[Regularity Lemma, minimum degree form]\label{lem:plex:reg} For all positive $\eps$, $d$ and $\gamma$ with $0<\epsr_1$ vertices with minimum degree $\delta(G)\ge\gamma n$ has an $(\eps,d)$-reduced graph~$R$ on $r$ vertices such that $r\le r_1$ and $\delta(R)\ge(\gamma-d-\eps)r$. \end{lemma} Lemma \ref{lem:plex:reg} is an easy consequence of the original Regularity Lemma of Szemer\'edi~\cite{Szem78}. Its proof can be found, for example, in~\cite[Proposition~9]{KuOsTa05}. Now we outline our proof strategy for Theorem~\ref{thm:main}. First, we apply Lemma \ref{lem:plex:reg} to a~given $n$-vertex graph $G$ with minimum degree at least $\gamma n$ and obtain the reduced $r$-vertex graph $R$ whose minimum degree is almost as large as $\gamma r$. Then we need to distinguish two cases. \underline{Case 1:} Some component of $R$ has less than $2\delta(R)$ vertices, and therefore contains a triangle. Using this triangle we will find a small triangulation $T$ (that is, a plane graph whose every face is a triangle) in $G$, and Theorem~\ref{thm:KOTquad} will guarantee a subgraph $S$ of the rest of the graph $G-V(T)$ such that the disjoint union of $S$ and $T$ has at least $2n$ edges. \underline{Case 2:} Each component of $R$ has at least $2\delta(R)>r/(k+1)$ vertices, and thus $R$ has at most $k$ components. These components correspond to $k$ well-connected subgraphs of $G$ and cover almost all vertices of $G$. In each subgraph we will find a quadrangulation (a plane graph whose every face has four edges) which has a certain `accepting' property that allows the few remaining vertices to be inserted. We conclude that there is a collection of at most $k$ vertex-disjoint quadrangulations covering all the vertices of~$G$. Since every quadrangulation on $m$ vertices has $2m-4$ edges, the theorem follows. As one can see from the above outline, our argument divides into two cases, depending on whether the reduced graph $R$ has a small component or not. In each case we shall need some embedding results, which we now describe in detail. When the reduced graph $R$ does have a small component, we will need the following embedding result, an easy case of the Counting Lemma (see, for example, Theorem 2.1 in~\cite{KS96}). \begin{lemma}\label{lem:count} For each $d>0$ and $s\in\NATS$ there exist $\eps>0$ and $m_0$ such that whenever $m\ge m_0$ the following holds. Let $U,V,W$ be three pairwise disjoint vertex sets each of size $m$. Suppose that each pair forms an $(\eps,d)$-regular pair in a graph $G$. Then $G$ contains every $3$-partite triangulation on $s$ vertices. \end{lemma} In the case that $R$ has no small components, we will construct quadrangulations. For this we shall use a version of the Blow-up Lemma. In order to state this result, we need a further definition. A pair of disjoint sets of vertices $U$ and $W$ in a graph $G$ is called \emph{$(\eps,\delta)$-super-regular} if it is $\eps$-regular, each vertex $u\in U$ has at least $\delta |W|$ neighbours in $W$, and each $w\in W$ has at least $\delta |U|$ neighbours in~$U$. The original version of the Blow-up Lemma, due to Koml\'os, S\'ark\"ozy and Szemer\'edi~\cite{KSS97}, showed that, for the purposes of embedding graphs of bounded degree, super-regular pairs behave like complete bipartite graphs. In our proof, we will need to embed (planar) graphs with growing degrees, which is generally a very difficult problem. Fortunately for us, planar graphs are examples of arrangeable graphs, for which a suitable extension of the Blow-up Lemma~\cite{KSS97} has recently been proven by B\"ottcher, Kohayakawa, Taraz and W\"urfl. \begin{definition}[$a$-arrangeable] \label{def:plex:arrangeable} Let $a$ be an integer. An $n$-vertex graph is called $a$-arrange\-able if its vertices can be ordered as $(x_1,\dots ,x_n)$ in such a way that \[ \left|N\Big(N(x_i)\cap\{x_{i+1}, x_{i+2},\dots, x_n\}\Big) \cap \{x_1, x_2,\dots, x_i \}\right| \le a \] for each $1 \le i \le n$. Here, for a set of vertices $S$, we denote by $N(S)$ the set of those vertices not in $S$ that are adjacent to some vertex in $S$. \end{definition} Chen and Schelp showed that planar graphs are $761$-arrangeable \cite{CheShe93}; Kierstead and Trotter \cite{KieTro93} improved this to $10$-arrangeable. Thus, the following theorem of B\"ottcher, Kohayakawa, Taraz and W\"urfl~\cite{BKTW_blowup} can be used to embed planar graphs whose maximum degree is not too large. \begin{theorem}[Arrangeable Blow-up Lemma] \label{thm:Blow-up:arr:plex} For all $a,\Delta_R,\kappa \in \NATS$ and for all $\delta>0$ there exists $\eps>0$ such that for every integer $r$ there is $n_0$ such that the following is true for every $n_1,\dots,n_r$ with $n_0\le n = \sum n_i$ and $n_i \le \kappa\cdot n_j$ for all $i,j\in[r]$. Let $R$ be a graph of order $r$ with $\Delta(R)<\Delta_R$. Assume that we are given a graph $G$ with a partition $V(G)=V_1\dcup\dots\dcup V_r$ and a graph $H$ with a partition $V(H)=X_1\dcup\dots\dcup X_r$ with $|V_i|=|X_i|=n_i$ such that $(V_i,V_j)$ is an $(\eps,\delta)$-super-regular pair for every $ij\in E(R)$ and such that all edges of $H$ run between sets $X_i,X_j$ for which $ij\in E(R)$. Further assume that $H$ is $a$-arrangeable and has $\Delta(H)\le \sqrt{n}/\log n$. Then there exists an embedding $\phi: V(H) \to V(G)$ of $H$ to $G$ such that $\phi(X_i)=V_i$. \end{theorem} %A spanning tree in a component of $R$ corresponds to a large well %connected subgraph of $G$. We will embed planar graphs into %spanning trees of components of $R$. However we need spanning trees whose %maximum degree is bounded: this is the purpose of the following lemma. We will embed planar graphs into large well connected subgraphs of $G$. These subgraphs will correspond to spanning trees of components of $R$. However, to be able to use Theorem \ref{thm:Blow-up:arr:plex}, we shall need spanning trees whose maximum degree is bounded. This is the purpose of the following lemma. \begin{lemma}\label{lem:spanbound} Given $k\in \NATS$, let $R$ be a connected graph with minimum degree at least $v(R)/k$. Then $R$ has a spanning tree with maximum degree $4k$. \end{lemma} \begin{proof} We define the \emph{score} of a spanning tree $T$ of $R$ to be the sum of the squares of the degrees of vertices in $T$. Let $T$ be a spanning tree of $R$ with minimum score. Observe that $T$ has less than $v(R)/(2k)$ vertices of degree $4k$, since the sum of the vertex degrees of $T$ is $2v(R)-2$. Suppose that there is a vertex $u$ of $T$ whose degree in $T$ exceeds $4k$. Observe that the removal of $u$ from $T$ disconnects $T$ into more than $4k$ components, one of which, $C$, has less than $v(R)/(4k)$ vertices. Let $v$ be the neighbour of $u$ which is in $C$. Now $v$ has at least $v(R)/k$ neighbours in $R$, of which less than $v(R)/(4k)$ are in $C$ and a further less than $v(R)/(2k)$ are of degree at least $4k$. It follows that $v$ has a neighbour $u'$ in $R$ which is not in $C$ and whose degree is less than $4k$. Let $T'$ be obtained from $T$ by deleting $uv$ and inserting $u'v$. Then $T'$ is still a spanning tree of $v$. Each vertex of $T'$ has the same degree as in $T$ except for $u$ and $u'$, which have respectively lost and gained one neighbour. It follows that the score of $T'$ is smaller than that of $T$, which by contradiction completes the proof. \end{proof} Finally, we need to specify which planar graphs we will embed into our spanning trees. Let $H=(V,E)$ be a plane graph. We say that a $k$ element subset $V'\subseteq V$ forms a \emph{bag of order $k$} in $H$ if there is $\{x_1,x_2\}\subseteq V\setminus V'$ such that $V'\cup\{x_1,x_2\}$ induces a copy of $K_{2,k}$ in $H$ and all inner faces of $H[V'\cup\{x_1,x_2\}]$ are also faces of $H$. We call the vertices of $V'$ which are not in the outer face the \emph{interior vertices} of the bag. \begin{figure}[ht] \begin{center} \begin{tikzpicture}[inner sep=1.75pt] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \node[label=270:$x_1$] (0) at (0,0) {}; \node (1) at (-2.2,1) {}; \node[label=180:$u$] (2) at (-1.2,1) {}; \node (3) at (-.4,1) {}; \node (4) at (.4,1) {}; \node[label=0:$u'$] (5) at (1.2,1) {}; \node (6) at (2.2,1) {}; \node[label=90:$x_2$] (7) at (0,2) {}; \node[label=270:$x_1$] (8) at (6,0) {}; \node (9) at (3.8,1) {}; \node (10) at (4.5,1) {}; \node (11) at (5.1,1) {}; \node[label=180:$u$] (12) at (5.8,1) {}; \node[label=0:$u'$] (13) at (7.2,1) {}; \node (14) at (8.2,1) {}; \node[label=90:$x_2$] (15) at (6,2) {}; \node (16) at (6.35,.5) {}; \node (17) at (6.35,.7) {}; \node (18) at (6.35,.9) {}; \node (19) at (6.35,1.1) {}; \node (20) at (6.35,1.3) {}; \node (21) at (6.35,1.5) {}; \draw[black,thick] (1) -- (0) -- (2) -- (7) -- (3) -- (0) -- (4) -- (7) -- (5) -- (0) -- (6) -- (7) -- (1) (9) -- (8) -- (10) -- (15) -- (11) -- (8) -- (12) -- (15) -- (13) -- (8) -- (14) -- (15) -- (9); \draw[black] (12) -- (16) -- (13) -- (17) -- (12) -- (18) -- (13) -- (19) -- (12) -- (20) -- (13) -- (21) -- (12); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \foreach \i in {0,...,15} { \fill[black!80] (\i) circle (3pt); } \foreach \i in {16,...,21} { \fill[black!80] (\i) circle (2pt); } \end{tikzpicture} \caption{A bag of order $k=6$; the same bag reordered and with an insertion of $\ell=6$ vertices.} \label{fig:sub:bags} \end{center} \end{figure} Observe that we can reorder the interior vertices of a bag without affecting the planarity of $H$. A bag is thus a very convenient structure into which one can put further vertices: if some vertex $v$ (not in $H$) is adjacent in a supergraph $G$ of $H$ to any two interior vertices $u,u'$ of a~bag, then we can redraw $H$ such that $u$ and $u'$ are consecutive in the bag, and insert $v$ and $uv,u'v$ to obtain $H'$. If $H$ is a quadrangulation, then $H'$ is still a quadrangulation contained in $G$. Furthermore, if $v_1,\ldots,v_\ell\notin V(H)$ are all adjacent to $u$ and $u'$ in $G$, then we can insert all these vertices and edges to $u$ and $u'$, and still obtain a subgraph $H''$ of $G$ which is a quadrangulation. Furthermore, $v_1,\ldots,v_\ell$ then form a~bag of order $\ell$ in $H''$. This will be particularly useful in the proof of the following lemma. \begin{lemma} \label{lem:blow-up-of-tree} Let $T$ be a tree of order $r\ge 2$, $n\ge (16r)^3$, and let $G$ be an $n$-vertex graph with the partition $V_1\dcup\dots\dcup V_r$ of its vertex set such that $|V_i|\le 2|V_j|$ for all $i\neq j$ and $G[V_i,V_j]$ is a complete bipartite graph whenever $ij\in E(T)$. Then $G$ contains a plane quadrangulation $H$ with maximum degree $\Delta(H)\le n^{1/3}+2$ as a spanning subgraph. Furthermore, all but at most $9 n^{2/3}$ vertices of $H$ are contained in a collection of pairwise disjoint bags each of order in the interval $[n^{1/3}/2, n^{1/3}]$. \end{lemma} \begin{proof} We first prove that $G$ has a quadrangulation $H$ with $\Delta(H)\le n^{1/3}+2$ by induction on $r$. So assume that $r=2$ and $G$ is a bipartite graph with partite sets $V_1,V_2$. We partition $V_i$ into a minimum number of sets $W_{i,j}$ with sizes $|W_{i,j}|\le n^{1/3}$ as equal as possible. The plane graph $H$ is constructed as follows. Take $x_1,x_2\in W_{1,1}$ and all of $W_{2,1}$ and embed the graph induced by these vertices into the plane. Let $y_1,y_2\in W_{2,1}$ lie in the same face and embed $W_{1,1}\setminus \{x_1,x_2\}$ into this face connecting each vertex to $y_1$ and $y_2$. We continue greedily embedding sets $W_{i,j}$ into faces with two vertices of degree 2 from $V_{3-i}$ and adding all edges in between. This process does not stop before all vertices of $G$ have been embedded into the plane. The resulting graph $H$ is a quadrangulation with $\Delta(H)\le n^{1/3}+2$. Now assume that $r>2$ and $1r\in E(T)$. Further assume that we have embedded $V_1\dcup \dots\dcup V_{r-1}$ this way and obtained a quadrangulation $H'$ on $V\setminus V_r$. We extend $H'$ to a quadrangulation $H$ on $V$ as follows. Again partition $V_r$ into a minimum number of sets $W_{r,i}$ with sizes $|W_{r,i}|\le n^{1/3}$ as equal as possible. For each $i$ sequentially, pick a pair of vertices $u, u'$ in $V_1$ that have degree 2 and lie in the same face in $H'$, embed all vertices from $W_{r,i}$ into this face, and connect these to $u, u'$. Since $|V_1|\ge n/(2r-1)> 8n^{2/3}$, we do not run out of pairs in~$V_1$. It remains to show that most vertices lie in a collection of large disjoint bags. Recall that the planarity of $H$ is preserved if we reorder the embedding in such a way that all vertices in $W_{i,j}$ of degree~2 in $H$ form a bag. Since there are at most $2n^{2/3}$ many sets $W_{i,j}$, all but at most $4n^{2/3}$ many vertices lie in pairwise disjoint bags. Some of these bags might be small, i.e., they might have order less than $\tfrac{1}{2}n^{1/3}$. Assume that the bag in $W_{i,j}$ is small. Note that $|W_{i,j}|\ge \tfrac{9}{10}n^{1/3}$ by construction. Thus at least $\tfrac15 n^{1/3}$ pairs from $W_{i,j}$ have been used to embed other sets $W_{i',j'}$. But there are at most $2n^{2/3}$ many sets $W_{i,j}$. Hence, at most $10n^{1/3}$ bags are small. Consequently, all but at most $4n^{2/3}+10n^{1/3}\cdot \tfrac{1}{2}n^{1/3}\le 9 n^{2/3}$ vertices lie in disjoint bags of size at least~$\tfrac12 n^{1/3}$. % Choose another two vertices of $W_{1,1}$ that lie in the same face and have degree 2 and embed all vertices of $W_{2,2}$ into this face again connecting all new vertices to the two previously embedded ones. We continue embedding $W_{i,j}$ \end{proof} \section{Proof of Theorem~\ref{thm:main}} Given $\gamma>0$, let $k\in \NATS$ be such that $k\le 1/(2\gamma)r/(k+1)$ vertices. It follows that $R$ has $c\le k$ components. We will show that we can cover $G$ with $c$ vertex-disjoint quadrangulations, which implies that $G$ contains a planar subgraph with at least $2n-4c\ge 2n-4k$ edges as required. Let $C$ be a component of $R$, and $T$ be its spanning tree with maximum degree $8(k+1)$ guaranteed by Lemma~\ref{lem:spanbound}. Let $V_i$ be any cluster of $C$ and $ij\in T$. Observe that, by the $(\eps, d)$-regularity of $(V_i, V_j)$, at most $\eps |V_i|$ vertices do \emph{not} have at least $(d-\eps)|V_j|$ neighbours in $V_j$. It follows that we can remove from each cluster $V_i$ at most $8(k+1)\eps|V_i|$ vertices and obtain a set $V'_i$ whose every vertex has at least $(d-\eps)|V_j|$ neighbours in each $V_j$ such that $ij\in T$. Since $(8(k+1)+1)\eps\le\beta/8$ and $d-\delta=\beta/8$, if $ij\in T$, then each vertex in $V_i'$ has at least $\delta |V'_j|$ neighbours in $V'_j$. Moreover, since $8(k+1)\eps\le 1/2$, for each $i$ we have $|V'_i|\ge |V_i|/2$. Consequently, the pair $(V'_i,V'_j)$ is $2\eps$-regular (see~\cite[Fact 1.5]{KS96}) and, since $|V_i|=|V_j|$, we also have $|V'_i|\le 2|V'_j|$ for each $i,j$. It follows that each edge $ij$ of $T$ corresponds to a $(2\eps,\delta)$-super-regular pair $(V'_i,V'_j)$, and the cluster sizes are not too unbalanced, as required for Theorem~\ref{thm:Blow-up:arr:plex}. Let $G'$ be a graph whose vertex set is the union of the sets $V'_i$, $i\in C$ and whose edges are all edges between $V'_i$ and $V'_j$ whenever $ij\in T$. Note that $G'$ has $n_C$ vertices, where $n_C$ satisfies $$ n\ge n_C\geq 2\delta(R)\big(1-8(k+1)\eps\big)\frac{(1-\eps)n}{r}\ge \frac{n}{2k}\ge n_0. $$ By Lemma~\ref{lem:blow-up-of-tree}, $G'$ contains a plane quadrangulation $H$ in which the maximum degree is at most ${n_C}^{1/3}+2\le n^{1/3}+2$, and in which at most $9n_C^{2/3}$ vertices are not contained in bags of order between $\tfrac12 {n_C}^{1/3}\geq (n/16k)^{1/3}$ and $n_C^{1/3}\le n^{1/3}$. By Theorem~\ref{thm:Blow-up:arr:plex}, $H$ can be embedded into the subgraph of $G$ induced on $\bigcup C$. Repeating this for each component we obtain a collection of $c$ vertex disjoint quadrangulations $H_1,\ldots,H_c$ in $G$, together with a collection $B_1,\ldots,B_\ell$ of pairwise disjoint bags of order at least $(n/16k)^{1/3}$ covering all but at most $9\sum_{C}n_C^{2/3}\le 9n^{2/3}k$ vertices of $\bigcup_{i\in[r]}V'_i$. In particular, we have that $\tfrac12n^{2/3}<\ell\le (16k)^{1/3}n^{2/3}$. Let $L$ be the set of vertices in none of the quadrangulations. Observe that every vertex in $L$ is either in $V_0$ or in $V_i\setminus V'_i$ for some $i$; therefore, it follows that $|L|\le(8(k+1)+1)\eps n$. We say that a bag $B_i$ is \emph{good} for $u\in L$ if $u$ has at least $n^{1/3}/(32k^2)$ neighbours in $B_i$. Since $(8(k+1)+1)\eps n+9n^{2/3}k\le\beta n$, each vertex $u\in L$ has at least $n/(2(k+1))$ neighbours contained in $B_1\cup\cdots\cup B_\ell$. Of these at least $n/(2(k+1))-\ell\cdot n^{1/3}/(32k^2)\ge n/(6k)$ lie in bags that are good for $u$. Hence, at least $n^{2/3}/(6k)\ge\ell/(24k^2)$ of the bags $B_i$ are good for $u$. We now assign vertices $L_i$ of $L$ to each bag $B_i$ sequentially as follows. From the collection of unassigned vertices of $L$ for which $B_i$ is good, we assign $L_i$ to be any $n^{1/3}/(128k^2)$ of them if this is possible, and all of them if not. Suppose that after carrying out this procedure there is a vertex $u$ of $L$ which is not in any $L_i$. Then it must be the case that for each $B_i$ good for $u$, we have $|L_i|=n^{1/3}/(128k^2)$. But there are at least $\ell/(24k^2)$ such $B_i$, and $\ell/(24k^2)\cdot n^{1/3}/(128k^2)>(8(k+1)+1)\eps n\ge|L|$, (where the first inequality is by choice of $\eps$) which is a contradiction. We then work as follows. For each bag $B_i$, we reorder the interior vertices of $B_i$ such that the first vertex of $L_i$ is adjacent to the first and second interior vertices of $B_i$, the second vertex of $L_i$ to the third and fourth, and so on. Because each vertex of $L_i$ has at least $n^{1/3}/(32k^2)$ neighbours in $B_i$, and $|L_i|\le n^{1/3}/(128k^2)$, this is possible. We now insert, for each $j$, the $j$th vertex of $L_i$ into the interior face of $B_i$ containing the $(2j-1)$st and $2j$th interior vertices, and add the edges to those two vertices. Let the plane graphs so constructed be $H'_1,\ldots,H'_c$. By construction, these graphs are vertex disjoint and cover $G$, and since $H_i$ was a quadrangulation, so $H'_i$ is also a quadrangulation for each $i$. The disjoint union of $H'_1,\ldots,H'_c$ is then a planar subgraph of $G$ with $2n-4c\ge 2n-4k$ edges, as required. \section{Concluding Remarks} There remain several open questions on planar graphs. In particular, it is possible that in Theorem~\ref{thm:main} the constant $n_\gamma$ can be taken to be an absolute constant provided $\gamma\gg n^{-1/2}$. Note that this is a natural lower bound since there are bipartite graphs without $4$-cycles of minimum degree $\Theta(n^{1/2})$. Another possibility would be to investigate the behaviour of the planarity function $\pl(n,\gamma n)$ for $\gamma\in(1/2,2/3]$ in more detail. Finally, one could ask these questions if the constraint imposed is that of edge density rather than minimum degree. More generally, one could replace `planar graphs' by some other property --- topologically defined, or by forbidden minors, for example. \subsection*{Acknowledgement} The third author would like to thank the London School of Economics for their hospitality while this work was being completed. %%%% BIB %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{10} \bibitem{BKTW_blowup} J.~B\"ottcher, Y.~Kohayakawa, A.~Taraz, and A.~W\"urfl, \emph{An extension of the {B}low-up {L}emma to arrangeable graphs}, \arxiv{1305.2059}. \bibitem{CheShe93} G.~Chen and R.~H. Schelp, \emph{Graphs with linearly bounded {R}amsey numbers}, J.~Combin. Theory Ser. B \textbf{57} (1993), no.~1, 138--149. \bibitem{CLTW12} O.~Cooley, T.~\L{}uczak, A.~Taraz, and A.~W\"urfl, \emph{Large planar subgraphs in dense graphs}, in preparation, 2013. \bibitem{ErdSto46} P.~Erd\H{o}s and A.~H. Stone, \emph{On the structure of linear graphs}, Bull. Amer. Math. Soc. \textbf{52} (1946), 1087--1091. \bibitem{KieTro93} H.~A. Kierstead and W.~T. Trotter, \emph{Planar graph coloring with an uncooperative partner}, J.~Graph Theory \textbf{18} (1994), no.~6, 569--584. \bibitem{KSS97} J.~Koml{\'o}s, G.~N. S{\'a}rk{\"o}zy, and E.~Szemer{\'e}di, \emph{Blow-up {L}emma}, Combinatorica \textbf{17} (1997), no.~1, 109--123. \bibitem{KS96} J.~Koml{\'o}s and M.~Simonovits, \emph{Szemer\'edi's regularity lemma and its applications in graph theory}, Combinatorics, Paul Erd\H os is eighty, Vol.\ 2 (Keszthely, 1993), Bolyai Soc. Math. Stud., vol.~2, J\'anos Bolyai Math. Soc., Budapest, 1996, pp.~295--352. \bibitem{KuhOst05} D.~K\"uhn and D.~Osthus, \emph{Spanning triangulations in graphs.}, J.~Graph Theory \textbf{49} (2005), no.~3, 205--233. \bibitem{KuOsTa05} D.~K{\"u}hn, D.~Osthus, and A.~Taraz, \emph{Large planar subgraphs in dense graphs}, J.~Comb. Theory, Ser. B \textbf{95} (2005), no.~2, 263--282. \bibitem{Niki11} V.~Nikiforov, \emph{Some new results in extremal graph theory}, \arxiv{1107.1121}. \bibitem{Szem78} E.~Szemer{\'e}di, \emph{Regular partitions of graphs}, Probl\`emes combinatoires et th\'eorie des graphes (Orsay, 1976), Colloques Internationaux CNRS, vol. 260, CNRS, 1978, pp.~399--401. \end{thebibliography} \end{document}