1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs

Červenková, Eliška; Kratochvíl, Jan

doi:10.4230/LIPIcs.GD.2025.26

1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs

Eliška Červenková

Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic Jan Kratochvíl

Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

Abstract

Matchstick graphs are graphs that allow plane embedding with straight edges of equal length. One-planar unit distance graphs are graphs that allow a drawing in the plane in which all edges are straight-line segments of equal length and every edge crosses at most one other edge. The maximum number of edges of a matchstick graph (1-planar unit distance graph) of order $n$ is denoted by $u_{0}(n)$ ( $u_{1}(n)$ , respectively). It is known that $u_{0}(n)=\lfloor 3n-\sqrt{12n-3}\rfloor$ holds for every $n$ . At GD’24, Gehér and Tóth proved a slightly weaker upper bound on $u_{1}(n)$ , but noted that no 1-planar unit distance graph $G$ with more than $u_{0}(|V(G)|)$ vertices was known. They asked if $u_{1}(n)=u_{0}(n)$ holds for every $n$ . We give a negative answer to this question in a much stronger way. We show that $u_{1}(n)>u_{0}(n)$ for every $n\geq 16135$ . Furthermore, we show that the gap between $u_{1}(n)$ and $u_{0}(n)$ can be arbitrarily large by proving that for $n$ large enough with respect to a constant $\alpha<\sqrt[4]{\frac{1}{3}}$ , $u_{1}(n)-u_{0}(n)\geq\alpha\sqrt[4]{n}$ .

Keywords and phrases:

planar graph, unit distance graph, matchstick graph, 1-planar graph

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Graph theory

Acknowledgements:

We thank the anonymous reviewers for valuable comments that helped increase the readability of the article.

Funding:

Both authors gratefully acknowledge support by grant No. 23-04949X of the Czech Science Foundation (GAČR).

DOI:

10.4230/LIPIcs.GD.2025.26

Event:

33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Editors:

Vida Dujmović and Fabrizio Montecchiani

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

We consider unit distance geometric graphs, i.e., graphs drawn in the plane in such a way that edges are drawn as straight line segments of equal (unit) length. As usual, vertices are embedded as points, and no vertex may lie on an edge, unless being one of its end-vertices. We are interested in the following two subclasses of such graphs. Matchstick graphs are plane unit distance graphs, i.e., graphs that allow a unit distance embedding with no edge crossings. A more general class is formed by 1-planar unit distance graphs, which allow unit distance drawings such that any edge is crossed by at most one other edge.

Matchstick graphs were introduced by Harborth in 1981 [4]. He conjectured that a matchstick graph on $n$ vertices has at most $\left\lfloor 3n-\sqrt{12n-3}\right\rfloor$ edges. As an answer to the problem of Reutter [9], he actually proved his conjecture in the case when the distance of any two vertices of the graph is greater than or equal to 1 already in 1974 [3]. In the same paper, Harborth also showed that the bound is tight by constructing, for every positive integer $n$ , a matchstick graph on $n$ vertices that achieves this upper bound. However, the conjecture itself has only recently been proved by Lavollée and Swanepoel [8]. Although this answers completely the question of the maximum number of edges of a matchstick graph, there are many other open research questions. Quite a lot of attention has been paid to regular matchstick graphs [1], [5], [6], [7]. To complete the picture, let us mention the article by Salvia [10], which serves as a catalog of small examples, as well as the articles by Winkler [11] and by Winkler, Dinkelacker, and Vogel [12], [13], [14], [15], which provide an overview of the diversity of matchstick graphs.

Gehér and Tóth [2] considered 1-planar unit distance graphs. They observed an interesting phenomenon with regard to the maximum possible number of edges. Although general 1-planar $n$ -vertex graphs (i.e., when the lengths of the edges are not required to be equal, and the edges need not be straight) may have as many as $4n-8$ edges compared to planar graphs having at most $3n-6$ edges, for unit distance graphs the coefficient of the linear term is the same. They showed that every 1-planar unit distance graph with $n$ vertices has at most $3n-\frac{1}{10}\sqrt[4]{n}$ edges. At the same time, they pointed out that no construction of a 1-planar unit distance graph with more edges than a matchstick graph on the same number of vertices was known. They denoted by $u_{0}(n)$ ( $u_{1}(n)$ ) the maximum number of edges of a matchstick (1-planar unit distance, respectively) graph on $n$ vertices, and they have explicitly asked this open question.

Question [Problem 12 in [2]].

Is it true that $u_{0}(n)=u_{1}(n)$ for every $n$ ?

We first provide a negative answer to this question by exhibiting the graph depicted in Fig. 2 middle. This 1-planar unit distance graph has 31 vertices and 74 edges, while $u_{0}(31)=73$ . The main goal of this paper is to strengthen this answer by showing that if the number of vertices is large enough, 1-planar unit distance graphs always beat matchstick graphs in the number of edges.

Theorem 1.

For every $n\geq 16135$ , $u_{1}(n)>u_{0}(n)$ .

We further show that the gap between $u_{0}(n)$ and $u_{1}(n)$ widens as $n$ tends to infinity.

Theorem 2.

For any constant $\alpha<\sqrt[4]{\frac{1}{3}}=.7598\ldots$ and for every $n$ sufficiently large (with respect to $\alpha$ ), $u_{1}(n)-u_{0}(n)\geq\alpha\sqrt[4]{n}$ .

In the next sections, we prove these theorems using an explicit construction. In both cases, we first construct an infinite sequence of 1-planar unit distance graphs with large numbers of edges. These graphs arise as a combination of two patterns: a duplicated square grid in the core part of the graph, and two triangular grids attached to the top and bottom sides of the core. The sizes of the grids are carefully chosen to balance the trade-offs of the boundary effect of the two types of grids. The numbers of vertices of these graphs will form a sparse subset of the set of positive integers. In the second step, we show how to fill the gaps by fine-tuning the first construction by adding a few (some of them partial) layers to the triangular grids in order not to lose too much from the surplus of the number of edges before reaching the next graph in the main sequence.

2 The construction

2.1 Small cases

On $n=6$ vertices, there are three non-isomorphic matchstick graphs with $u_{0}(6)=9$ edges (see Fig. 1). There exists another non-isomorphic unit distance graph $F$ depicted in Fig. 2 left. Note that this triangular prism graph is not a matchstick graph. However, it clearly is a 1-planar unit distance graph, as can be seen from drawing its vertices as points with coordinates $(0,0),(1,0),(0,1),(1,1),(\frac{1}{2},\frac{\sqrt{3}}{2}),(\frac{1}{2},1+\frac{% \sqrt{3}}{2})$ . Concatenating five overlapping copies of $F$ and adding a top and a bottom path of equilateral triangles yields the ad hoc graph depicted in Fig. 2 middle. This is the smallest example of a 1-planar unit distance graph with more edges than a matchstick graph that we know of. It has 31 vertices and 74 edges, while $u_{0}(31)=\lfloor 93-\sqrt{372-3}\rfloor=\lfloor 93-19.2...\rfloor=73$ .

Refer to caption — Figure 1: Three non-isomorphic matchstick graphs with $6$ vertices and $9$ edges.

2.2 Putting the prisms together

The graph from Fig. 2 middle contains all the ingredients of the general construction. The five copies of the prism graph $F$ with the additional horizontal edges form a $1\times 5$ square grid coupled with a shifted $1\times 4$ one. A path $T_{4}$ of triangles is added on the top, and a path $T_{5}$ on the bottom (a path of triangles $T_{n}$ is depicted in Fig. 2 right). The general construction is as follows. We build graphs $G_{t,k,a}$ , parameterized by three parameters: $k$ refers to the number of $k+1$ copies of the elementary building block $F$ concatenated in a row, $t$ is the number of such rows stacked on top of each other (to be precise, half of them stacked on top of each other, and the other half added below them in a reflection along the horizontal axis), and $a$ is the number of paths of triangles stacked above (and below) the rows of $F$ ’s. We will then tune the parameters $k$ and $a$ to achieve the best comparison with the maximum possible number of edges of a matchstick graph on the same number of vertices. We will show that the “well tuned” graphs “win” over $u_{0}(n)$ by $t$ edges. Of course, the numbers of vertices given by this construction are very specific.

Let us now describe the construction in full detail. Note that $t$ will always be even. To construct the graph $G_{t,k,a}$ , begin with $k+1$ copies of $F$ , denoted by $F^{1,i}$ for $i\in\{1,2,\ldots,k+1\}$ , with the corresponding vertex sets $\{v_{j}^{1,i}:j=1,2,\ldots,6\}$ . The larger graph $F^{(1\times k+1)}$ is formed by identifying the following vertices: $v_{2}^{1,i}=v_{1}^{1,i+1}$ and $v_{4}^{1,i}=v_{3}^{1,i+1}$ for $i\in\{1,2\ldots,k\}$ . Additionally, for each $i\in\{1,2,\ldots,k\}$ , we include the edges $v_{5}^{1,i}v_{5}^{1,i+1}$ and $v_{6}^{1,i}v_{6}^{1,i+1}$ .

All edges in $F^{(1\times k+1)}$ are represented by unit-length line segments. The only intersecting edges are of the form $v_{2}^{1,i}v_{4}^{1,i}$ and $v_{5}^{1,i}v_{5}^{1,i+1}$ for $i\in\{1,2,\ldots,k\}$ , and $v_{5}^{1,j}v_{6}^{1,j}$ and $v_{3}^{1,j}v_{4}^{1,j}$ for $j\in\{1,2,\ldots,k+1\}$ . Hence, $F^{(1\times k+1)}$ remains a 1-planar unit distance graph.

As previously stated, the graph $F$ contains $6$ vertices and $9$ edges. Each additional copy of $F$ contributes $4$ new vertices and $10$ edges because of the identifications made during the construction. Therefore, the graph $F^{(1\times k+1)}$ consists of $6+4k$ vertices and $9+10k$ edges.

In the next step, add a copy of $F^{(1\times k+1)}$ with corresponding vertices $v_{j}^{2,i}$ for $j\in\{1,\ldots,6\},i\in\{1,2,\ldots,k+1\}$ and identify the vertices $v_{1}^{2,i}=v_{3}^{1,i}$ , $v_{2}^{2,i}=v_{4}^{1,i}$ , and $v_{5}^{2,i}=v_{6}^{1,i}$ . Denote the resulting graph by $F^{(2\times k+1)}$ . This procedure is referred to as adding a row to $F^{(1\times k+1)}$ . It adds $3+2k$ vertices and $6+6k$ edges.

Repeat the above-described step $\left(\frac{t}{2}-1\right)$ times. Since each step adds a new row, for the resulting graph $F^{(\frac{t}{2}\times k+1)}$ , it holds that

		$\displaystyle\|V(F^{(\frac{t}{2}\times k+1)})\|\begin{aligned} &=6+4k+\left(% \frac{t}{2}-1\right)(3+2k)=3+2k+\frac{3t}{2}+kt,\end{aligned}$		(1)
		$\displaystyle\|E(F^{(\frac{t}{2}\times k+1)})\|\begin{aligned} &=9+10k+\left(% \frac{t}{2}-1\right)(6+6k)=3+4k+3t+3kt.\end{aligned}$		(1)

In the next step, attach a trapezoid consisting of $a$ paths of triangles (the bottom one being $T_{k}$ and the top one being $T_{k-a+1}$ ) to the graph $F^{(\frac{t}{2}\times k+1)}$ in such a way that the bottom side of the trapezoid coincides with the upper horizontal side of $F^{(\frac{t}{2}\times k+1)}$ . Denote the resulting graph by $F_{t,k,a}$ .

It holds that

		$\displaystyle\|V(F_{t,k,a})\|\begin{aligned} &=\|V(F^{(\frac{t}{2}\times k+1)})\|+% \sum_{\ell=k}^{k-a+1}\ell=3+2k+\frac{3t}{2}+kt+\frac{(2k-a+1)a}{2}=\\ &=ka-\frac{(a-1)a}{2}+3+2k+\frac{3t}{2}+kt,\\ \end{aligned}$		(2)
		$\displaystyle\|E(F_{t,k,a})\|\begin{aligned} &=\|E(F^{(\frac{t}{2}\times k+1)})\|+% \sum_{\ell=k}^{k-a+1}(3\ell-1)=3+4k+3t+3kt+3\sum_{\ell=k}^{k-a+1}\ell-a=\\ &=3+4k+3t+3kt+\frac{3(2k-a+1)a}{2}-a=\\ &=3ak+\frac{-3a^{2}+a}{2}+3+4k+3t+3kt.\end{aligned}$		(2)

In the final step, the graph $G_{t,k,a}$ is obtained by reflecting $F_{t,k,a}$ across a horizontal axis and identifying the corresponding horizontal sides of length $k+1$ .

Proposition 3.

For every three positive integers $a, k$ and $t$ , where $t$ is even, $G_{t,k,a}$ is a 1-planar unit distance graph with $2ka-a^{2}+a+4+3k+3t+2tk$ vertices and $6ka-3a^{2}+a+5+7k+6t+6kt$ edges.

Proof.

A 1-planar unit distance drawing of $G_{t,k,a}$ can be built along the lines of its definition. For the numbers of vertices and edges, note that $G_{t,k,a}$ is built by joining two copies of $F_{t,k,a}$ (the original and the flipped one) and these two copies share $k+2$ vertices and $k+1$ edges. Hence, $|V(G_{t,k,a})|=2|V(F_{t,k,a})|-(k+2)=2ka-a^{2}+a+4+3k+3t+2tk$ and $|E(G_{t,k,a})|=2|E(F_{t,k,a})|-(k+1)=6ka-3a^{2}+a+5+7k+6t+6kt$ . $\hfill\blacktriangleleft$

Finally, we choose a specific dependence of $k$ on $a$ and $t$ , namely, $k=2a+t+1$ , and set $H_{t,a}=G_{t,2a+t+1,a}$ . It is not important for the main result, but we note that this choice optimizes the gain of $|E(G_{t,k,a})|$ over $u_{0}(|V(G_{t,k,n})|)$ . This can be shown by standard methods in calculus. In the sequel, we set $n(t,a)=|V(H_{t,a})|=3a^{2}+9a+6at+7+8t+2t^{2}$ . Note that $|E(H_{t,a})|=9a^{2}+21a+18at+12+19t+6t^{2}$ .

Proposition 4.

For every even positive integer $t$ and every $a\geq t^{2}$ , $|E(H_{t,a})|-u_{0}(n(t,a))\geq t$ .

Proof.

For $a=t^{2}$ , we have

		$\displaystyle\|V(H_{t,t^{2}})\|=n(t,t^{2})=3t^{4}+6t^{3}+1t^{2}+8t+7,$		(3)
		$\displaystyle\|E(H_{t,t^{2}})\|=9t^{4}+8t^{3}+7t^{2}+9t+2=3n(t,t^{2})-(6t^{2}+5t% +9)$		(3)

and

\displaystyle|E(H_{t,t^{2}})|-u_{0}(n(t,t^{2}))\begin{aligned} &=3n(t,t^{2})-(% 6t^{2}+5t+9)-\lfloor 3n(t,t^{2})-\sqrt{12n(t,t^{2})-3}\rfloor\geq\\ &\geq 3n(t,t^{2})-(6t^{2}+5t+9)-(3n(t,t^{2})-\sqrt{12n(t,t^{2})-3})=\\ &=\sqrt{12n(t,t^{2})-3}-(6t^{2}+5t+9)>t-1.\\ \end{aligned}

(4)

The last inequality follows from

\sqrt{12n(t,t^{2})-3}>6t^{2}+6t+8

which is equivalent to

	$\displaystyle 2n(t,t^{2})-3$	$\displaystyle=6t^{4}+2t^{3}+32t^{2}+6t+1>$
		$\displaystyle>6t^{4}+2t^{3}+(6+6)t^{2}+6t+4=(6t^{2}+6t+8)^{2}.$

Denote

	$\displaystyle f_{t}(x)$	$\displaystyle=9x^{2}+1x+8xt+2+9t+6t^{2}-$
		$\displaystyle-(3(3x^{2}+9x+6xt+7+8t+2t^{2})-\sqrt{12(3x^{2}+9x+6xt+7+8t+2t^{2}% )-3})=$
		$\displaystyle=\sqrt{12(3x^{2}+9x+6xt+7+8t+2t^{2})-3}-(6x+5t+9)$

for a real variable $x$ . Note that $|E(H_{t,a})|-u_{0}(n(t,a))\geq f_{t}(a)$ for every positive integer $a$ . We claim that $f_{t}(x)$ is increasing for $x>0$ for every $t>0$ . This follows from the first derivative in $x$ . A simple calculation shows that

\displaystyle\dfrac{df_{t}}{dx}

\displaystyle=-6+\frac{1}{2}\cdot\frac{72x+108+72t}{\sqrt{36x^{2}+108x+72xt+81% +96t+24t^{2}}}>0

(5)

is equivalent to $12t^{2}+12t>0$ , which is true for all $t>0$ .

Since $f_{t}(x)$ is increasing and $f_{t}(t^{2})>t-1$ as we have seen above, we have

|E(H_{t,a})|-u_{0}(n(t,a))\geq f_{t}(a)>t-1

(6)

for every $a\geq t^{2}$ . And since $|E(H_{t,a})|-u_{0}(n(t,a))$ is an integer, we get

|E(H_{t,a})|-u_{0}(n(t,a))\geq t

(7)

for every $a\geq t^{2}$ . $\hfill\blacktriangleleft$

Corollary 5.

For every integer $t$ , there are infinitely many values $n$ such that $u_{1}(n)-u_{0}(n)\geq t$ . Hence $\limsup_{n\to\infty}(u_{1}(n)-u_{0}(n))=\infty$ .

2.3 Proof of Theorem 1

In this subsection, we will show how to fill the gaps between consecutive $n(t,a)$ and $n(t,a+1)$ for which we know, by Proposition 4, that $u_{1}(n(t,a))>u_{0}(n(t,a))$ and $u_{1}(n(t,a+1))>u_{0}(n(t,a+1))$ . For each $n\in\{n(t,a)+1,\ldots,n(t,a+1)-1\}$ , we will construct a graph $L_{t,n}$ by adding $n-n(t,a)$ vertices to $H_{t,a}$ (see the detailed description below). The following observation will be quite useful to argue about the gain of $L_{t,n}$ over $u_{0}(n)$ .

Lemma 6.

Let $G_{0},G_{1},\ldots,G_{n}$ be a sequence of graphs such that for every $i=1,\ldots,n$ , $G_{i}$ is obtained from $G_{i-1}$ by adding a vertex $x_{i}$ of degree 2 or 3. Then $|E(G_{n})|-u_{0}(|V(G_{n})|)\geq|E(G_{0})|-u_{0}(|V(G_{0})|)-k$ , where $k=|\{i:\mbox{deg}_{G_{i}}x_{i}=2\}|$ .

Proof.

Let us denote by $n_{i}=n_{0}+i$ the number of vertices of $G_{i}$ , $i=0,1,\ldots,n$ . Observe that

u_{0}(n_{i})=\lfloor 3n_{0}+3i-\sqrt{12n_{i}-3}\rfloor\leq\lfloor 3n_{0}+3i-% \sqrt{12n_{0}-3}\rfloor\leq u_{0}(n_{0})+3i.

Adding the vertex $x_{i}$ to $G_{i-1}$ adds 2 or 3 edges, depending on $\mbox{deg}_{G_{i}}x_{i}$ . Thus,

|E(G_{n})|=|E(G_{0})|+3n-k

for $k=|\{i:\mbox{deg}_{G_{i}}x_{i}=2\}|$ . Putting these two together, we obtain

|E(G_{n})|-u_{0}(n_{n})=|E(G_{0})|+3n-k-u_{0}(n_{n})\geq

\geq|E(G_{0})|+3n-k-u_{0}(n_{0})-3n=|E(G_{0})|-u_{0}(n_{0})-k.\

$\hfill\blacktriangleleft$

Proof of Theorem 1.

Fix an even integer $t,t\geq 8$ and examine two consecutive graphs $H_{t,a}$ and $H_{t,a+1}$ . For $n\in\left\{|V(H_{t,a})|,|V(H_{t,a+1})|\right\}$ , our construction guarantees a graph $G$ on $n$ vertices such that $|E(G)|-u_{0}(n)\geq t.$ Since the goal is to extend the construction to cover values of $n$ strictly between $|V(H_{t,a})|$ and $|V(H_{t,a+1})|$ , we recall the number of vertices in both graphs explicitly:

		$\displaystyle\|V(H_{t,a})\|=3a^{2}+9a+6at+7+8t+2t^{2},$		(8)
		$\displaystyle\|V(H_{t,a+1})\|\begin{aligned} &=3a^{2}+15a+19+6at+14t+2t^{2}.\end% {aligned}$		(8)

The number of vertices that separate $H_{t,a}$ from $H_{t,a+1}$ is

		$\displaystyle\|V(H_{t,a+1})\|-\|V(H_{t,a})\|=3a^{2}+5a+9+6at+4t+2t^{2}-$		(9)
		$\displaystyle-(3a^{2}+9a+6at+7+8t+2t^{2})=6a+6t+2.$		(9)

The geometric structure of $H_{t,a}$ , which has a perimeter of the shape of an octagon with horizontal sides of length $a+1+t$ , will be further exploited. Attaching a path of triangles $T_{\ell}$ to a horizontal side of length $\ell$ contributes $\ell$ vertices and $3\ell-1$ edges. This implies that by adding these vertices one by one, we add 1 vertex of degree 2 and then $\ell-1$ vertices of degree 3. By Lemma 6, such an addition of vertices decreases the edge surplus by at most one.

Suppose further that $a\geq t^{2}$ . Then $a\geq t^{2}>2t$ , as $t\geq 8$ is assumed. Then attach paths of triangles $T_{a+1+t}$ , $T_{a+t}$ and $T_{a+t-1}$ to the upper horizontal side of $H_{t,a}$ , and $T_{a+1+t}$ , $T_{a+t}$ , $T_{a+t-1}$ and $T_{a+t-2}$ to the bottom horizontal side of $H_{t,a}$ . This operation adds:

	$\displaystyle 2(a+1+t+(a+t)+(a+t-1))+(a+t-2)=7a-2+7t=$
	$\displaystyle=6a+a-2+6t+t\geq 6a-2+6t+3t>6a+6t+3$

vertices, which is more than enough to cover the gap computed in (9).

Assume that an integer $n\in\{|V(H_{t,a})|,\ldots,|V(H_{t,a+1})|\}$ is given. Construct the graph $L_{t,n}$ by adding the rows attached to $H_{t,a}$ from above and below, until the number of vertices is $n$ (the last row added may remain unfinished). The resulting graph is shown in Fig. 6.

In total, we have added at most 7 vertices of degree 2, the remaining ones were all of degree 3. Lemma 6 implies that

|E(L_{t,n})|-u_{0}(n)\geq|E(H_{t,a})|-u_{0}(|V(H_{t,a})|)-7\geq t-7\geq 1

(10)

as $t\geq 8$ is assumed.

This implies that for every even integer $t,t\geq 8$ , for all $n\geq|V(H_{t,t^{2}})|$ , there exists a graph $L_{t,n}$ on $n$ vertices satisfying

|E(L_{t,n})|-u_{0}(n)\geq 1.

Substituting the smallest values for $a$ and $t$ , which means $t=8$ and $a=64$ , we get

|V(H_{8,64})|=3\cdot 64^{2}+9\cdot 64+6\cdot 64\cdot 8+7+8\cdot 8+2\cdot 8^{2}% =16135.

Therefore, for all $n\geq 16135$ , there exists a 1-planar unit distance graph on $n$ vertices with more edges than any matchstick graph on the same number of vertices has. $\hfill\blacktriangleleft$

The proof has the following useful corollary.

Corollary 7.

For every even positive integer $t\geq 8$ and for every $n\geq n(t,t^{2})$ , $u_{1}(n)-u_{0}(n)\geq t-7$ .

Proof.

If $n\geq n(t,t^{2})$ , then $n\in\{n(t,a),\ldots,n(t,a+1)-1\}$ for some $a\geq t^{2}$ . Then (10) implies that $u_{1}(n)-u_{0}(n)\geq t-7$ . $\hfill\blacktriangleleft$

2.4 Proof of Theorem 2

In this subsection, we show a lower bound on the growth rate of the surplus $u_{1}(n)-u_{0}(n)$ as $n$ tends to infinity. We utilize the construction from the previous subsection. Again, we first show that the bound from Theorem 2 holds for infinitely many isolated values of $n$ , and then fill the gaps. Let $\alpha<\sqrt[4]{\frac{1}{3}}$ be an arbitrary positive constant from the statement of the theorem and let $\beta$ be another constant, $\alpha<\beta<\sqrt[4]{\frac{1}{3}}$ . The constants $\alpha$ and $\beta$ stay fixed for the rest of this subsection. We use the notation $n(t,a)=|V(H_{t,a})|=3a^{2}+9a+6at+7+8t+2t^{2}$ which was introduced in Subsection 2.2.

Proposition 8.

For sufficiently large $t$ , we have $t\geq\beta\sqrt[4]{n(t,t^{2})}$ .

Proof.

Extend the function $n(t,t^{2})=3t^{4}+6t^{3}+11t^{2}+8t+7$ , which has so far been defined only for even positive integers $t$ , to all positive real values of $t$ . For $n=n(t,t^{2})$ , Wolfram Alpha tells us (and it can then be easily checked by hand) that $t$ can be expressed as

t=\frac{1}{6}\left(\sqrt{12\sqrt{3n-5}-39}-3\right).

It follows that

t=\sqrt{\sqrt{\frac{n}{3}-\frac{5}{9}}-\frac{39}{36}}-\frac{1}{2}\geq\beta% \sqrt[4]{n}

holds for sufficiently large $n$ (and hence also for sufficiently large $t$ ), as long as $\beta<\sqrt[4]{\frac{1}{3}}$ . $\hfill\blacktriangleleft$

Proof of Theorem 2.

Let $t_{0}\geq 8$ be an even integer large enough, so that

t_{0}-7\geq\frac{\alpha}{\beta}(t_{0}+2)\mbox{ and }t_{0}\geq\beta\sqrt[4]{n(t% _{0},t_{0}^{2})}.

(Since the involved functions are monotone, it follows that

t-7\geq\frac{\alpha}{\beta}(t+2)\mbox{ and }t\geq\beta\sqrt[4]{n(t,t^{2})}

hold for every $t\geq t_{0}$ .)

For every $n\geq n(t_{0},t_{0}^{2})$ , there is an even integer $t$ such that $n(t,t^{2})\leq n<n(t+2,(t+2)^{2})$ . Then, using this $t$ , it follows from Corollary 7 and Proposition 8 that

u_{1}(n)-u_{0}(n)\geq t-7\geq\frac{\alpha}{\beta}(t+2)\geq\frac{\alpha}{\beta}% \beta\sqrt[4]{n(t+2,(t+2)^{2})}>\alpha\sqrt[4]{n}.\

$\hfill\blacktriangleleft$

3 Conclusion

We have answered in negative the question of Gehér and Tóth, who asked if $u_{1}(n)=u_{0}(n)$ for every $n$ by showing that for every large enough $n$ , the difference $u_{1}(n)-u_{0}(n)$ is at least as large as $\alpha\sqrt[4]{n}$ for any constant $\alpha<\sqrt[4]{\frac{1}{3}}$ . It is interesting that a function of the same growth rate appears in the upper bound for $u_{1}(n)$ proven by Gehér and Tóth. In fact, their result can be reformulated as $3n-u_{1}(n)\geq\frac{\sqrt[4]{n}}{10}$ . Is this a coincidence?

All our examples of 1-planar unit distance graphs are non-planar. This invokes the following open problem (which seems to have been asked during the discussion at Graph Drawing ’24).

Problem 1.

Does there exist a planar graph which has a 1-planar unit distance drawing and which has more edges than any matchstick graph on the same number of vertices?

Also all our examples allow for 1-planar unit distance drawings in which only vertical and horizontal edges cross. Define $u_{0.5}(n)$ as the maximum number of edges of such an $n$ -vertex graph.

Problem 2.

Prove an upper bound on $u_{0.5}(n)$ better than $3n-c\sqrt[4]{n}$ .

Problem 3.

Is $u_{0.5}(n)<u_{1}(n)$ for some $n$ ? For infinitely many $n$ ’s?

References

[1] Aart Blokhuis. Regular finite planar maps with equal edges, 2019. doi:10.48550/arXiv.1401.1799.
[2] Panna Gehér and Géza Tóth. 1-Planar Unit Distance Graphs. In Stefan Felsner and Karsten Klein, editors, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024), volume 320 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:9. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.GD.2024.6.
[3] Heiko Harborth. Lösung zu Problem 664A. Elem. Math., 29:14–15, 1974.
[4] Heiko Harborth. Point sets with equal numbers of unit-distance neighbors (Abstract). In Discrete Geometry, Oberwolfach, Tagungsbericht 31/1981, pages 11–12. Mathematisches Forschungsinstitut Oberwolfach, 1981.
[5] Sascha Kurz. A lower bound for 4-regular planar unit distance graphs. Geombinatorics Quarterly, 21:63–72, 2011. doi:10.48550/arXiv.1401.4377.
[6] Sascha Kurz and Giuseppe Mazzuoccolo. 3-regular matchstick graphs with given girth. Geombinatorics Quarterly, 19:156–173, 2009. doi:10.48550/arXiv.1401.4360.
[7] Sascha Kurz and Rom Pinchasi. Regular matchstick graphs. The American Mathematical Monthly, 118:264–267, 2011. doi:10.4169/amer.math.monthly.118.03.264.
[8] Jérémy Lavollée and Konrad Swanepoel. A tight bound for the number of edges of matchstick graphs. Discrete Computational Geometry, 72:1530–1544, 2023. doi:10.1007/s00454-023-00530-z.
[9] O. Reutter. Problem 664A. Elem. Math., 27:19, 1972.
[10] Raffaele Salvia. A catalog of matchstick graphs, 2015. doi:10.48550/arXiv.1303.5965.
[11] Mike Winkler. A catalog of 4-regular matchstick graphs with 63 - 70 vertices, 2017. doi:10.48550/arXiv.1705.04715.
[12] Mike Winkler, Peter Dinkelacker, and Stefan Vogel. Minimal completely asymmetric (4; $n$ )-regular matchstick graphs, 2016. doi:10.48550/arXiv.1609.06972.
[13] Mike Winkler, Peter Dinkelacker, and Stefan Vogel. New minimal (4; $n$ )-regular matchstick graphs. Geombinatorics Quarterly, 27:26–44, 2017. doi:10.48550/arXiv.1604.07134.
[14] Mike Winkler, Peter Dinkelacker, and Stefan Vogel. On the existence of 4-regular matchstick graphs, 2017. doi:10.48550/arXiv.1705.00293.
[15] Mike Winkler, Peter Dinkelacker, and Stefan Vogel. A 3-regular matchstick graph of girth 5 consisting of 54 vertices. Geombinatorics Quarterly, 29:116–121, 2019. doi:10.48550/arXiv.1903.04304.

[bib.bib1] [1] Aart Blokhuis. Regular finite planar maps with equal edges, 2019. doi:10.48550/arXiv.1401.1799.

[bib.bib2] [2] Panna Gehér and Géza Tóth. 1-Planar Unit Distance Graphs. In Stefan Felsner and Karsten Klein, editors, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024), volume 320 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:9. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.GD.2024.6.

[bib.bib3] [3] Heiko Harborth. Lösung zu Problem 664A. Elem. Math., 29:14–15, 1974.

[bib.bib4] [4] Heiko Harborth. Point sets with equal numbers of unit-distance neighbors (Abstract). In Discrete Geometry, Oberwolfach, Tagungsbericht 31/1981, pages 11–12. Mathematisches Forschungsinstitut Oberwolfach, 1981.

[bib.bib5] [5] Sascha Kurz. A lower bound for 4-regular planar unit distance graphs. Geombinatorics Quarterly, 21:63–72, 2011. doi:10.48550/arXiv.1401.4377.

[bib.bib6] [6] Sascha Kurz and Giuseppe Mazzuoccolo. 3-regular matchstick graphs with given girth. Geombinatorics Quarterly, 19:156–173, 2009. doi:10.48550/arXiv.1401.4360.

[bib.bib7] [7] Sascha Kurz and Rom Pinchasi. Regular matchstick graphs. The American Mathematical Monthly, 118:264–267, 2011. doi:10.4169/amer.math.monthly.118.03.264.

[bib.bib8] [8] Jérémy Lavollée and Konrad Swanepoel. A tight bound for the number of edges of matchstick graphs. Discrete Computational Geometry, 72:1530–1544, 2023. doi:10.1007/s00454-023-00530-z.

[bib.bib9] [9] O. Reutter. Problem 664A. Elem. Math., 27:19, 1972.

[bib.bib10] [10] Raffaele Salvia. A catalog of matchstick graphs, 2015. doi:10.48550/arXiv.1303.5965.

[bib.bib11] [11] Mike Winkler. A catalog of 4-regular matchstick graphs with 63 - 70 vertices, 2017. doi:10.48550/arXiv.1705.04715.

[bib.bib12] [12] Mike Winkler, Peter Dinkelacker, and Stefan Vogel. Minimal completely asymmetric (4; $n$ )-regular matchstick graphs, 2016. doi:10.48550/arXiv.1609.06972.

[bib.bib13] [13] Mike Winkler, Peter Dinkelacker, and Stefan Vogel. New minimal (4; $n$ )-regular matchstick graphs. Geombinatorics Quarterly, 27:26–44, 2017. doi:10.48550/arXiv.1604.07134.

[bib.bib14] [14] Mike Winkler, Peter Dinkelacker, and Stefan Vogel. On the existence of 4-regular matchstick graphs, 2017. doi:10.48550/arXiv.1705.00293.

[bib.bib15] [15] Mike Winkler, Peter Dinkelacker, and Stefan Vogel. A 3-regular matchstick graph of girth 5 consisting of 54 vertices. Geombinatorics Quarterly, 29:116–121, 2019. doi:10.48550/arXiv.1903.04304.