<p>A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_752_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_n\)</EquationSource> </InlineEquation> admits a plane Hamiltonian cycle. It turned out that already the existence of much simpler non-crossing substructures in such drawings is hard to prove. Recent progress was made by Aichholzer et al. and by Suk and Zeng who proved the existence of a plane path of length <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_752_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="126" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Omega (\log n / \log \log n)\)</EquationSource> </InlineEquation> and of a plane matching of size <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_752_Article_IEq3.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Omega (n^{1/2})\)</EquationSource> </InlineEquation> in every simple drawing of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_752_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{n}\)</EquationSource> </InlineEquation>. Instead of studying simpler substructures, we prove Rafla’s conjecture for the subclass of convex drawings, the most general class in the convexity hierarchy introduced by Arroyo et al. Moreover, we show that every convex drawing of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_752_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_n\)</EquationSource> </InlineEquation> contains a plane Hamiltonian path between each pair of vertices (Hamiltonian connectivity) and a plane <i>k</i>-cycle for each <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="454_2025_752_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">\(3 \le k \le n\)</EquationSource> </InlineEquation> (pancyclicity), and present further results on maximal plane subdrawings.</p>

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

Plane Hamiltonian Cycles in Convex Drawings

  • Helena Bergold,
  • Stefan Felsner,
  • Meghana M. Reddy,
  • Joachim Orthaber,
  • Manfred Scheucher

摘要

A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph \(K_n\) admits a plane Hamiltonian cycle. It turned out that already the existence of much simpler non-crossing substructures in such drawings is hard to prove. Recent progress was made by Aichholzer et al. and by Suk and Zeng who proved the existence of a plane path of length \(\Omega (\log n / \log \log n)\) and of a plane matching of size \(\Omega (n^{1/2})\) in every simple drawing of \(K_{n}\) . Instead of studying simpler substructures, we prove Rafla’s conjecture for the subclass of convex drawings, the most general class in the convexity hierarchy introduced by Arroyo et al. Moreover, we show that every convex drawing of \(K_n\) contains a plane Hamiltonian path between each pair of vertices (Hamiltonian connectivity) and a plane k-cycle for each \(3 \le k \le n\) (pancyclicity), and present further results on maximal plane subdrawings.