Given a complete simple topological graph G, a k-face generated by G is the open bounded region enclosed by the edges of a non-self-intersecting k-cycle in G. Interestingly, for any number n there is a complete simple topological graph G with n vertices such that every odd face generated by G contains the origin. In this paper, we show that every complete n-vertex simple topological graph generates at least <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\Omega (n^{1/3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> pairwise disjoint 4-faces. As an immediate corollary, every complete simple topological graph on n vertices drawn in the unit square generates a 4-face with area at most <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(n^{-1/3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mo>-</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Finally, we investigate a <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathbb {Z}_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">Z</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> variant of Heilbronn’s triangle problem for not necessarily simple complete topological graphs.

Disjoint Faces in Drawings of the Complete Graph and Topological Heilbronn Problems

期刊论文
发表日期：

2025年2月20日

查看全文

Alfredo Hubard,
Andrew Suk

摘要

Given a complete simple topological graph G, a k-face generated by G is the open bounded region enclosed by the edges of a non-self-intersecting k-cycle in G. Interestingly, for any number n there is a complete simple topological graph G with n vertices such that every odd face generated by G contains the origin. In this paper, we show that every complete n-vertex simple topological graph generates at least $\Omega (n^{1/3})$ $Ω (n^{1 / 3})$ pairwise disjoint 4-faces. As an immediate corollary, every complete simple topological graph on n vertices drawn in the unit square generates a 4-face with area at most $O(n^{-1/3})$ $O (n^{- 1 / 3})$ . Finally, we investigate a $\mathbb {Z}_2$ $Z_{2}$ variant of Heilbronn’s triangle problem for not necessarily simple complete topological graphs.