Minimum number of common edges of triangulations

Question

Let $S$ and $T$ be two triangulations. We define $c(S,T)$ as the number of edges shared by $S$ and $T$.

With this, we can define

$f(n) = \min_{P} \min_{S,T} c(S,T)$.

Here the first minimum goes over all point sets in the plane of size $n$ and the second minimum goes over all triangulations $S$ and $T$ on $P$.

What do we know about $f(n)$? I am looking both for upper and lower bounds. I also would like to know what is currently known. In other words, I am looking for references, as the problem appears natural to me, and I expect that it might have been studied before.

I find particularly interesting the case that the convex hull of the point set is a triangle.

Answer 1

Modifying Alex Ravsky's excellent construction, we can get rid of the $O(k)$ shared horizontal and vertical edges. Four new vertices are placed far enough from the original figure, suitably aligned and suitably connected. This construction shows that $f(k^2+4) \le 8$.

---

EDIT. I'm getting the hunch six would always suffice. Gerry Myerson already commented that $f(7) \le 6$. Findings from random point configurations, with six points fixed at a hexagon's corners, show that $f(n) \le 6$ for $n=8,9,10,11$ (pictures below; only the external edges are shared). Perhaps someone with more inspiration can think of a general construction. (To complement, Tony Huynh's answer has thoughts about lower bounds.)

$f(8) \le 6$:

$f(9) \le 6$:

$f(10) \le 6$:

$f(11) \le 6$:

Answer 2

By Theorem 1 from [DGM], for each $n\ge 9$, there exists a geometric thickness-two graph with $n$ vertices and $6n − 19$ edges. When we partition this graph into two straight-edged planar graphs and triangulate each of them, we obtain two triangulations with at most $7$ common edges, which implies $f(n)\le 7$. Taras Banakh proposed the pattern which is promising to show that $f(n)\le 6$ or maybe even that $f(n)\le 5$, but I am surviving a deadline now so I have to postpone this project.

References

[DGM] Stephane Durocher, Ellen Gethner, Debajyoti Mondal, Thickness and colorability of geometric graphs, Computational Geometry 56 (2016) 1-18.

Answer 3

This question was considered in On representations of some thickness-two graphs by Hutchinson, Shermer, and Vince. They define a graph to be doubly linear if it is the union of two straight-edged planar graphs (with the same vertex embedding). For each $n \geq 4$, they prove that an $n$-vertex doubly linear graph has at most $6n-18$ edges. Thus, any two triangulations of an $n$-point set in the plane must contain at least 6 common edges.

If you do not insist that the outerface is a triangle, then their results imply that there must be at least 5 common edges. In particular, they prove that if the outerface contains exactly 4 points, then there must be at least two additional edges in common between any two triangulations. I could not modify their proof method to show that if the outerface contains exactly 5 points, then there must be an additional edge in common.

They also find the same nice constructions given by Jukka Kohonen, Brendan McKay, and Alex Ravsky in the other answers, as visibility graphs of rectangles. See Figures 3 and 4 in the linked paper.

Thus, for all $n \geq 10$, $f(n) \in \{5,6,7,8\}$

Answer 4

Note that it is possible to remove one or two points (maybe more) from Jukka's construction while retaining only 8 common lines. For example, removing the top left vertex of the array can be done like this (thanks, Jukka, for the image). If Alex's suggestion to use a rectangular array is factored in, I bet that all point counts can be achieved.