Scholarlink

<p>Distel, Dujmović, Eppstein, Hickingbotham, Joret, Micek, Morin, Seweryn and Wood conjectured that every <i>n</i>-vertex planar graph <i>G</i> is a subgraph of the strong product of an apex-forest and a complete graph of order <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(\sqrt{n})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msqrt> <mi>n</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we prove a weaker version of this conjecture, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(O(\sqrt{n})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msqrt> <mi>n</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is replaced by <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(O(\sqrt{kn})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msqrt> <mrow> <mi mathvariant="italic">kn</mi> </mrow> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <i>k</i> is the maximum length of a cycle within a BFS<InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="MediaObjects/40840_2026_2106_IEq4_HTML.gif" Format="GIF" Height="7" Rendition="HTML" Resolution="120" Type="Linedraw" Width="7" /> </InlineMediaObject> </InlineEquation> layer.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Product Structure for Planar Graphs

  • 期刊论文

  • 发表日期：

    2026年4月29日

查看全文
  • Lingyu Lv,
  • Huayue Liu

摘要

Distel, Dujmović, Eppstein, Hickingbotham, Joret, Micek, Morin, Seweryn and Wood conjectured that every n-vertex planar graph G is a subgraph of the strong product of an apex-forest and a complete graph of order \(O(\sqrt{n})\) O ( n ) . In this paper, we prove a weaker version of this conjecture, where \(O(\sqrt{n})\) O ( n ) is replaced by \(O(\sqrt{kn})\) O ( kn ) and k is the maximum length of a cycle within a BFS layer.