Triangular faces in convex rectilinear drawings of complete graphs

Abstract

In a convex rectilinear drawing of Kₙ the n vertices are points in strictly convex position, no three of them collinear, and every edge is drawn as a straight segment; a k-face is a bounded face of the resulting figure, a convex polygon with k corners, and t₃ denotes the number of triangular faces. Balko, Brötzner, Klute and Tkadlec asked for the minimum of t₃ over convex drawings, over generic convex drawings, and over the regular drawing, and observed that t₃ ≥ n(n-3) always. We prove that n(n-3) is exactly the number of faces whose closure contains a vertex of the drawing, that every such face is a triangle, and that the remaining triangular faces are in bijection with those 6-element subsets of the vertex set whose three main diagonals bound a face. Writing τ for the number of such subsets, this gives the exact splitting t₃=n(n-3)+τ, valid for every convex drawing. We then prove τ ≥ n-5 for n ≥ 5, which improves the known bound to t₃ ≥ n²-2n-5 and settles the generic minimum at n=5 and n=6, where it equals 10 and 19; on those two classes t₃ is in fact constant. For 4 ≤ n ≤ 14 we exhibit generic drawings with exactly 3C(n-2, 2)+1 triangular faces, so the generic minimum is at most that value, and we show that the conjecture that this value is optimal is equivalent to the inequality τ ≥ C(n-4, 2). All finite computations and all arithmetic identities reported here are machine-checked in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   f5cb1aa1fd2a569c7d81349950b25314f0359aae19c9f3b020ae0b2c3d165785