I. N. Mikhailov, “Planar locally minimal trees with boundaries on a circle”, Sb. Math., 215:5 (2024), 658

Processing math: 100%

Sbornik: Mathematics

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Forthcoming papers
	Archive
	Impact factor
	Guidelines for authors
	License agreement
	Submit a manuscript

	Search papers
	Search references

	RSS
	Latest issue
	Current issues
	Archive issues
	What is RSS

Mat. Sb.:
Year:
Volume:
Issue:
Page:
	Find

Personal entry:
Login:
Password:
	Save password
	Enter
	Forgotten password?
	Register

Sbornik: Mathematics, 2024, Volume 215, Issue 5, Pages 658–666
DOI: https://doi.org/10.4213/sm10002e (Mi sm10002)

Planar locally minimal trees with boundaries on a circle

I. N. Mikhailov

Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia

English version PDF (471 kB) HTML full-text Russian version article

References:

PDF

HTML

DOI: https://doi.org/10.4213/sm10002e

Abstract: A planar tree has a convex minimal realization if it is planar equivalent to a locally minimal tree whose boundary is the set of vertices of a convex polygon. If this polygon is inscribed in a circle, then the tree is said to have a circular minimal realization. We construct a wide class of planar trees that have convex minimal realizations but do not have circular ones.
Bibliography: 9 titles.

Keywords: full Steiner trees, Steiner minimal trees, Steiner problem, locally minimal trees, twisting number of a full planar Steiner tree.

Received: 21.09.2023 and 26.12.2023

Bibliographic databases:

Document Type: Article

MSC: Primary 05C05, 51F99; Secondary 05C10

Language: English

Original paper language: Russian

§ 1. Introduction

The well-known Steiner problem consists in seeking a shortest network spanning a finite set of points, which are called boundary points, in some ambient metric space. This problem is interesting first of all because of its numerous applications; in particular, it has a natural transport interpretation in the case of the ordinary Euclidean plane.

In many classes of metric spaces the local structure of shortest networks is known. For example, on an arbitrary Riemannian manifold edges of networks of this kind are geodesics (see [1] and [2]) and meet at vertices at angles of at least $2\pi/3$ . In particular, the degrees of all vertices are at most $3$ . Without loss of generality we can also assume that networks of this kind do not contain nonboundary vertices of degree $2$ , since geodesics meet at such points at an angle of $\pi$ and thus we can eliminate them from the vertex set by gluing the two incoming geodesics into a single one, which keeps the network to be shortest and does not change it as a subset of the manifold. In addition, by cutting an arbitrary shortest tree through boundary vertices of degrees above $1$ , we can reduce the Steiner problem on a Riemannian manifold to the case of full Steiner networks, that is, networks such that their sets of boundary vertices coincide with the sets of vertices of degree $1$ , and all nonboundary vertices have degree $3$ .

The problem of the construction of a shortest network spanning a given set of points is $\mathrm{NP}$ -complex (see [3]) even in the discrete case when all points in the boundary set and in the network to be constructed are assumed to have integer coordinates, and it admits a polynomial solution algorithm only when the network topology is known.

Hence the problem of the description of all shortest networks spanning a given set of points is generally very difficult.

A natural extension of the class of shortest networks is the class of locally shortest networks, which are shortest in a neighbourhood of each point. Thus, these are precisely networks whose local structure is the same as that of shortest networks. In the case of the ordinary Euclidean plane, locally shortest networks are all possible planar graphs such that nonboundary vertices are of degree $3$ , boundary vertices are of degree at most $3$ , and edges are line segments that meet at vertices at angles of at least $2\pi/3$ (see [4] and [5]).

Ivanov and Tuzhilin [1], [2] presented a full description of planar Steiner trees with convex locally minimal realizations, that is, planar trees that are planar equivalent to a full Steiner tree spanning the vertices of a convex polygon. In addition to trees with convex boundaries, Ivanov and Tuzhilin also studied trees with regular (see [6]–[8]) and quasi-regular (see [9]) boundaries whose boundary vertices lie at the vertices of a regular polygon or on the successive arcs of the circumscribed circle of a regular polygon, respectively.

In this paper we consider planar trees having circular minimal realizations, or, more precisely, trees that are planar equivalent to some full Steiner tree spanning vertices of a convex inscribed polygon. A wide class of trees that have convex minimal realizations but do not have circular minimal realizations is described.

Acknowledgments

The author is grateful to his scientific advisor A. A. Tuzhilin for posing the problem and his constant attention to this research and also to A. V. Begunts and S. V. Shaposhnikov for involving him in scientific work and for their assistance in his search for an appropriate research topic.

§ 2. Basic definitions and preliminary results

We give the basic definitions and assertions; for detail, see [1] and [2].

A planar graph is called a planar tree if the corresponding combinatorial graph is a tree.

Note that when variational problems are studied, a finite subset of vertices, called boundary vertices, is distinguished on each tree, whereas other vertices are called interior vertices. Edges incident to at least one boundary vertex are also called boundary edges.

A full Steiner tree is a planar tree such that all of its vertices have degree $1$ or $3$ , the vertices of degree $1$ form the set of boundary vertices, and edges are line segments.

A full Steiner tree is locally minimal if at all of its vertices of degree $3$ edges meet at an angle of $2\pi/3$ .

A full Steiner tree has a convex locally minimal realization if there exists a planar-equivalent locally minimal full Steiner tree such that all of its boundary vertices are at vertices of some convex polygon.

A full Steiner tree has a circular minimal realization if it has a convex locally minimal realization such that all of its boundary vertices lie on some circle.

A path $\gamma$ in a planar tree $G$ is called oriented if one of the two natural orderings is fixed on its vertices.

We define oriented polygonal lines in a similar way. Note that edges of an oriented polygonal line can be considered as ordinary vectors on the plane.

We let $(e_1, e_2)$ denote the sequence of edges of the unique oriented path in a full Steiner tree $G$ such that its first edge coincides with $e_1$ and its last edge coincides with $e_2$ .

It is sometimes convenient to regard an edge $e$ in $(e_1, e_2)$ as a nonoriented edge of the original graph; in such a case this will be clear from the context.

By analogy, we let $(v_1, v_2)$ denote the sequence of vertices of the unique oriented path in a full Steiner tree $G$ such that its first and last vertices are $v_1$ and $v_2$ , respectively.

We fix the standard orientation on the plane.

We consider an arbitrary oriented path $\gamma$ in a full Steiner tree $G$ . We assign $+1$ to a pair of consecutive edges $e_1$ , $e_2$ in this path if the basis consisting of $e_1$ and $e_2$ is positively oriented, and we assign $-1$ otherwise. The sum of these numbers over all pairs of consecutive edges in $\gamma$ is called the twisting number of $\gamma$ and is denoted by $\operatorname{tw}(\gamma)$ (or by $\operatorname{tw}(e_1, e_2)$ , or $\operatorname{tw}(v_1, v_2)$ if the first and last edges in the path $\gamma$ are $e_1$ and $e_2$ or the first and last vertices of $\gamma$ are $v_1$ and $v_2$ , respectively). The greatest of the twisting numbers $\operatorname{tw}(\gamma)$ over all oriented paths $\gamma$ in $G$ is called the twisting number of $G$ and is denoted by $\operatorname{tw}(G)$ .

We consider an arbitrary oriented polygonal line $X_1X_2\dots X_n$ . The angle $\angle (X_iX_{i+1}, X_{i+1}X_{i+2})$ between two consecutive edges $X_iX_{i+1}$ and $X_{i+1}X_{i+2}$ of this line is the angle between the vectors $\overrightarrow{X_iX_{i+1}}$ , $\overrightarrow{X_{i+1}X_{i+2}}$ taken with the plus sign if $\operatorname{tw}(X_iX_{i+1},X_{i+1}X_{i+2})=1$ and with the minus sigh otherwise. The angle of rotation $\operatorname{rot}(X_1X_2\dots X_n)$ along the line $X_1X_2\dots X_n$ is defined as the sum $\sum_{i=1}^{n-2}\angle (X_iX_{i+1},\,X_{i+1}X_{i+2})$ .

Note that in the case when $G$ is a locally minimal full Steiner tree, the angle between any two consecutive edges in an arbitrary oriented path $\gamma$ is $\pm\pi/3$ , that is, $\operatorname{tw}(\gamma)= \operatorname{rot}(\gamma)/(\pi/3)$ .

We emphasize two elementary properties of the twisting number:

$\bullet$ (antisymmetry) $\operatorname{tw}(e_1, e_2)=-\operatorname{tw}(e_2, e_1)$ ;
$\bullet$ (additivity along paths) if an edge $e_2$ belongs to a path from $e_1$ to $e_3$ , then $\operatorname{tw}(e_1, e_3)=\operatorname{tw}(e_1, e_2)+\operatorname{tw}(e_2, e_3)$ .

Now we state two key well-known propositions concerning full locally minimal trees.

Proposition 1. If all vertices of degree $1$ of a full locally minimal Steiner tree lie on the boundary of a convex polygon, then the twisting number of $G$ is at most $5$ .

Proposition 2. Each full locally minimal Steiner tree lies in the convex hull of the set of its boundary points.

The following two simple statements, which we use in what follows, are also true.

Statement 1. If $G$ is a full Steiner tree, $\operatorname{tw}(G) \leqslant k$ , and edges $e$ and $f$ of this tree satisfy $\operatorname{tw}(e, f)=k$ , then $e$ and $f$ are boundary edges.

Statement 2. Assume that a full Steiner tree with twisting number $\operatorname{tw}(G)=5$ satisfies $\operatorname{tw}(e, e')=(-1)^k\,5$ , $k\in\mathbb{Z}$ , where $f$ and $f'$ are the second and penultimate edges in the sequence $(e, e')$ , and let $g$ and $g'$ be edges adjacent to the pairs of edges $e$ , $f$ and $e'$ , $f'$ respectively, but not coinciding with these edges. Then $\operatorname{tw}(e, f)=\operatorname{tw}(g', f')=\operatorname{tw}(e', g')=(-1)^k$ and $\operatorname{tw}(e', f')=\operatorname{tw}(g, f)=\operatorname{tw}(e, g)= (-1)^{k+1}$ .

Finally, we will use the following well-known fact.

Statement 3. The full angle of rotation along a closed non-self-intersecting polygonal line is $\pm2\pi$ depending on the direction chosen.

§ 3. Main result

Here we state and prove our main result.

Theorem. Let $\gamma=v_1 e_1 \dots v_2 \dots v_3 \dots e_4 v_4$ be a path in a full Steiner tree $G$ , where $v_1$ , $v_2$ , $v_3$ and $v_4$ are distinct vertices of $G$ , and $e_1$ and $e_4$ are some edges of $G$ . Let $e_2$ and $e_3$ denote the edges of $G$ that are incident to $v_2$ and $v_3$ , respectively, but do not belong to $\gamma$ . Assume that:

(1) $|{\operatorname{tw}( e_1, e_2)}|=|{\operatorname{tw} (e_3, e_4 )}|=5$ ;
(2) for any edge $e$ in the sequence $(e_2, e_3)$ the inequalities $\operatorname{tw}(e_2, e) \geqslant 0$ and $\operatorname{tw}(e_2, e_3)\neq 1$ hold.

Then the tree $G$ has no circular minimal realization.

Proof. Suppose that a tree

$G$ satisfying the assumptions of the theorem has a circular minimal realization; for convenience, we consider

$G$ as coinciding with this minimal realization.

Since a circular minimal realization is convex, Proposition 1 and Statement 1 immediately yield that $e_1$ , $e_2$ , $e_3$ and $e_4$ are boundary edges of $G$ .

Lemma 1. The equality $\operatorname{tw}(e_1, e_2)=5$ holds.

Proof. Suppose the converse. Let

$f$ be the penultimate edge in the sequence

$(e_1, e_2)$ and

$f'$ be the second edge in the sequence

$(e_2, e_3)$ . Since we assume that

${\operatorname{tw}(e_1, e_2)=-5}$ , we have

$\operatorname{tw}(f, e_2)=-1$ by Statement 2; hence

$\operatorname{tw}(e_2, f)=-\operatorname{tw}(f, e_2)=1$ . However, by assumption (2) of the theorem

$\operatorname{tw}(e_2, f')\geqslant 0$ , that is,

$\operatorname{tw}(e_2, f')=1$ since these two edges are adjacent. Thus,

$\operatorname{tw}(e_2, f')=\operatorname{tw}(e_2, f)=1$ , which implies that

$f$ coincides with

$f'$ ; this contradicts the fact that

$f'$ and

$f$ are consecutive edges in the path

$\gamma$ .

The lemma is proved.

Lemma 2. The equality $\operatorname{tw}(e_3, e_4)=-5$ holds.

Proof. Suppose the statement is not true and

$\operatorname{tw}(e_3, e_4)=5$ (Figure 1). Let

$f$ be the penultimate edge in the sequence

$(e_1, e_2)$ ,

$f'$ be the second edge in the sequence

$(e_2, e_3)$ ,

$e$ be the penultimate edge in the sequence

$(e_2, e_3)$ , and

$e'$ be the second edge in the sequence

$(e_3, e_4)$ .

Figure 1.An example for Lemma 2.

It follows from Statement 2 that

$\begin{equation*} \begin{gathered} \, \operatorname{tw}(f, e_2)=1, \qquad \operatorname{tw}(f, f')=-1, \qquad \operatorname{tw}(e_2, f')=1, \\ \operatorname{tw}(e_3, e')= 1, \qquad \operatorname{tw}(e, e')=-1, \qquad \operatorname{tw}(e_3, e)=-1. \end{gathered} \end{equation*} \notag$

We also have

$\begin{equation*} \operatorname{tw}(f', e)=\operatorname{tw}(e_2, e)-\operatorname{tw}(e_2, f')= \operatorname{tw}(e_2, e)-1\geqslant 0-1=-1. \end{equation*} \notag$

$\operatorname{tw}(f', e)=-1$ , then

$\begin{equation*} \operatorname{tw}(e_2, e_3)=\operatorname{tw}(e_2, f')+\operatorname{tw}(f', e)+\operatorname{tw}(e, e_3)=1-1+1=1, \end{equation*} \notag$

which contradicts the assumptions of the theorem. Therefore,

$\operatorname{tw}(f', e)\geqslant 0$ . Then

$\begin{equation*} \begin{aligned} \, \operatorname{tw}(e_1, e_4) &=\operatorname{tw}(e_1, f)+\operatorname{tw}(f, f')+ \operatorname{tw}(f', e)+\operatorname{tw}(e, e')+\operatorname{tw}(e', e_4) \\ &=4-1+ \operatorname{tw}(f', e)-1+4=6+\operatorname{tw}(f', e) \geqslant 6, \end{aligned} \end{equation*} \notag$

which, according to Proposition 1, contradicts the convexity of the realization under consideration.

The lemma is proved.

Lemma 3. The inequality $2 \geqslant \operatorname{tw}(e_2, e) \geqslant 0$ holds for any edge but $e_3$ in the sequence $(e_2, e_3)$ .

Proof. The second inequality holds by the assumptions of the theorem. We prove the first. Suppose there is an edge

$h$ in the sequence

$(e_2, e_3)$ distinct from

$e_3$ and such that

$\operatorname{tw}(e_2, h)=3$ . Then

$h$ is not a boundary edge; thus,

$\operatorname{tw}(e_2, g)=4$ , where

$g$ is one of the edges adjacent to it. Then

$\operatorname{tw}(e_1, g)=6$ , which contradicts the convexity of the realization under consideration according to Proposition 1.

The lemma is proved.

Lemma 4. The equality $\operatorname{tw}(e_2, e_3)=0$ holds.

Proof. It follows from Lemma 3 that

$\operatorname{tw}(e_2, e_3) \in \{-1, 0, 1, 2, 3\}$ . The assumption (2) of the theorem implies that

$\operatorname{tw}(e_2, e_3) \neq 1$ and

$\operatorname{tw}(e_2, e_3)\neq -1$ .

Let $e'$ be the second edge in the sequence $(e_3, e_4)$ and $e$ be the penultimate edge in the sequence $(e_2, e_3)$ . Since $\operatorname{tw}(e_3, e_4)=-5$ , we have $\operatorname{tw}(e_3, e)=1$ by Statement 2. Using the estimate $\operatorname{tw}(e_2, e)\leqslant 2$ from Lemma 3, we obtain

$\begin{equation*} \operatorname{tw}(e_2, e_3)=\operatorname{tw}(e_2, e)+\operatorname{tw}(e, e_3)= \operatorname{tw}(e_2, e)-1 \leqslant 2-1=1. \end{equation*} \notag$

Therefore,

$\operatorname{tw}(e_2, e_3)$ is

$0$ .

The lemma is proved.

Lemma 5. Let $P_1P_2\dots P_n$ be a convex polygon. Then all angles between consecutive edges of the polygonal line $P_1P_2\dots P_nP_1P_2$ are of the same sign.

Proof. Without loss of generality we assume that the angle between

$P_1P_2$ and

$P_2P_3$ is positive, whereas the one between

$P_2P_3$ and

$P_3P_4$ is negative. Note that

$P_4$ and

$P_1$ are on opposite sides of the line

$P_2P_3$ in this case. This is in contradiction with the fact that the polygon

$P_1P_2\dots P_k$ is convex.

The lemma is proved.

Lemma 6. Let $B$ be an arbitrary disc in the plane, $\partial B$ be the boundary of $B$ , $X_1X_2\dots X_n$ be a non-self-intersecting polygonal line $\gamma$ lying in $B$ such that ${\gamma\cap\partial B=\{X_1, X_n\}}$ , and let $\operatorname{rot}(\gamma)= 5\pi/3$ . Then the rays $X_2X_1$ and $X_{n-1}X_n$ intersect outside $B$ at an angle of $2\pi/3$ .

Proof. We show that it is possible to inscribe polygonal lines

$X_nP_1P_2\dots P_kX_1$ and

$X_nQ_1Q_2\dots Q_lX_1$ in the two arcs

$X_1X_n$ of

$\partial B$ so that each of these lines intersects

$\gamma$ only at the vertices

$X_1$ and

$X_n$ .

For subsets $A$ and $B$ in a metric space, we let $\rho(A,B)$ denote the infimum of the distances between arbitrary points $a\in A$ and $b\in B$ , that is, $\rho(A,B)= \inf\{|ab|\colon {a\in A,\,b\in B}\}$ .

We construct discs with centres $X_1$ and $X_n$ and radii below $\rho(X_1, \gamma\setminus[X_1X_2))$ and $\rho(X_n, \gamma\setminus[X_nX_{n-1}))$ , respectively. We choose points $Q'$ and $P'$ , and $Q_1$ and $P_1$ in the first and second discs, respectively, that lie on $\partial B$ in the same order in which the vertices $Q_k$ , $P_l$ , $Q_1$ and $P_1$ of the polygonal lines to be constructed must lie on $\partial B$ . After that it suffices only to inscribe polygonal lines in the arcs $\mathop{\smallsmile} P_1P'$ and $\mathop{\smallsmile} Q_1Q'$ so that their endpoints coincide with the vertices of these arcs and they do not intersect $\gamma$ . We construct a polygonal line of this type for the arc $\mathop{\smallsmile} P_1P'$ . Since $\mathop{\smallsmile} P_1P'$ and $\gamma$ are disjoint compact sets, the distance $d$ between them is positive. We subdivide the arc $\mathop{\smallsmile} P_1P'$ into subarcs of length below $d$ . Clearly, the endpoints of these subarcs arranged in the order from $P_1$ to $P'$ are the vertices of the required polygonal line.

We consider the polygons $X_1X_2\dots X_nP_1\dots P_k$ and $X_1X_2\dots X_nQ_1\dots Q_l$ and orient their boundaries in accordance with the above orderings of their vertices. It follows from the construction of the polygonal lines that the boundaries of $X_1X_2\dots X_nP_1\dots P_k$ and $X_1X_2\dots X_nQ_1\dots Q_l$ are of opposite orientations. By Statement 3 the full angle of rotation of just one of these polygons along its boundary is $2\pi$ . Without loss of generality we let $X_1X_2\dots X_nP_1\dots P_k$ be this polygon.

We denote the angles between consecutive edges of the oriented polygonal line $X_{n-1}X_nP_1 \dots P_kX_1X_2$ by $\alpha,\psi_1,\dots,\psi_k$ and $\beta$ , respectively. By the equalities $\operatorname{rot}(X_1X_2\dots X_nP_1\dots P_kX_1X_2)=2\pi$ and $\operatorname{rot}(\gamma)=5\pi/3$ we have $\alpha+\psi_1+\dots+\psi_k+ \beta=\pi/3$ . Applying Lemma 5 to the convex polygon $X_nP_1\dots P_kX_1$ , we conclude that all angles $\psi_1,\dots,\psi_k$ are of the same sign. From the construction of the polygonal line $X_nP_1\dots P_kX_1$ we see that $P_2$ does not lie on the arc $\mathop{\smallsmile}X_nP_1$ not containing $X_1$ . Hence $P_2$ lies in the same half-plane as $X_{n-1}$ with respect to the line $X_nP_1$ . It follows that the angles $\alpha$ and $\psi_1$ are of the same sign. Similarly, $\beta$ and $\psi_k$ are of the same sign. Therefore, all angles $\alpha,\psi_1,\dots,\psi_k$ and $\beta$ are of the same sign; by the above equality they are nonnegative.

We calculate the sum of the angles of the polygon $X_nP_1\dots P_kX_1$ in two ways. On the one hand the sum of its angles is $\pi k$ . On the other hand it is

$\begin{equation*} \angle X_1X_nP_1+(\pi -\psi_1)+\dots+(\pi-\psi_k)+\angle P_kX_1X_n. \end{equation*} \notag$

Thus,

$\begin{equation*} \pi k=\pi k-(\psi_1+\dots+ \psi_k)+\angle X_1X_nP_1+\angle P_kX_1X_n. \end{equation*} \notag$

That is, we have

$\begin{equation*} \angle X_1X_nP_1+\angle P_kX_1X_n= \psi_1+\dots+\psi_k. \end{equation*} \notag$

Since

$\alpha,\beta\geqslant 0$ , it follows that

$\begin{equation*} \angle X_2X_1X_n=\pi-\beta-\angle P_kX_1X_n, \qquad \angle X_1X_nX_{n-1}=\pi-\alpha-\angle X_1X_nP_1. \end{equation*} \notag$

Then

$\begin{equation*} \begin{aligned} \, \angle X_2X_1X_n+\angle X_1X_nX_{n-1} &=(\pi-\beta-\angle P_kX_1X_n)+(\pi-\alpha-\angle X_1X_nP_1) \\ &=2\pi-(\alpha+\beta+\psi_1+\dots+\psi_k)=2\pi-\frac{\pi}{3}=\frac{5\pi}{3}, \end{aligned} \end{equation*} \notag$

which implies that the rays

$X_2X_1$ and

$X_{n-1}X_n$ intersect at an angle of

$2\pi/3$ , as required.

Lemma 6 is proved.

We return to the proof of the theorem. Let $B$ be the disc whose boundary contains the boundary vertices of $G$ , and let the vertices of the edges $e_2$ and $e_3$ distinct from $v_2$ and $v_3$ be denoted by $w_2$ and $w_3$ , respectively (Figure 2).

Figure 2.Example for the proof of the theorem.

Applying Lemma 6 to the polygonal line $(v_1,w_2)$ we infer that the rays outgoing from $v_1$ and $w_2$ and parallel to the edges $e_1$ and $e_2$ , respectively, but not containing them intersect at an angle of $2\pi/3$ at some point $R$ outside $B$ . Then the larger arc cut out on $\partial B$ by the sides of the angle $\angle v_1Rw_2$ is at least $4\pi/3$ . Similarly, applying Lemma 6 to the polygonal line $(w_3,v_4)$ we infer that the rays from $w_3$ and $v_4$ that are parallel to the edges $e_3$ and $e_4$ , respectively, but do not contain them intersect at an angle of $2\pi/3$ at some point $S$ outside the disc $B$ and that the larger arc cut out on $\partial B$ by the sides of the angle $\angle w_3Sv_4$ is at least $4\pi/3$ . It follows from Lemma 4 that $e_2\parallel e_3$ ; therefore, the lines $Rv_2$ and $Sv_3$ are parallel.

Let $f'$ be the second edge in the sequence $(e_2,e_3)$ and $w$ be the vertex distinct from $v_2$ of this edge. Since $\operatorname{tw}(e_1,e_2)=5$ , we have $\operatorname{tw}(e_1,f')=3$ . Thus, the vector $\overrightarrow{v_1R}$ is codirected with the vector $\overrightarrow{v_2w}$ . It follows that $w$ and $v_1$ lie in distinct half-planes with respect to the line $v_2R$ . Lemma 3 yields that all oriented edges in the sequence $(e_2,e_3)$ have directions such that their projections onto the ray starting on the line $v_2R$ , orthogonal to it, and lying in the same half-plane as $w$ are nonnegative. Thus, all vertices but $w_2$ and $v_2$ of edges in the sequence $(e_2,e_3)$ lie in the distinct half-plane from $v_1$ with respect to the line $v_2R$ . In particular, this is true for $v_3$ . It follows from Lemmas 1, 2 and 4 that the vectors $\overrightarrow{v_1R}$ and $\overrightarrow{Sv_4}$ are codirected. Since $v_1$ and $v_3$ lie in distinct half-planes with respect to the line $v_2R$ , the extension of the ray $v_1R$ beyond the point $R$ intersects the line $Sv_3$ . This implies that the ray $Sv_4$ does not intersect the line $v_2R$ , that is, the angles $\angle v_1Rv_2$ and $\angle v_3Sv_4$ have disjoint interiors. It follows that the arcs cut out on $\partial B$ by these angles are also disjoint. Then the length of the circle $\partial B$ is at least the sum of the lengths of the two larger arcs cut out on $\partial B$ by the sides of these angles, that is, it at least $2\cdot4\pi/3 > 2\pi$ , which is a contradiction.

The theorem is proved.

Note that it is impossible to discard the condition $\operatorname{tw}(e_2, e_3)\neq 1$ . Consider the tree $T$ shown in Figure 3. The equalities $\operatorname{tw}(e_1,e_2)=\operatorname{tw}(e_3,e_4)=5$ and $\operatorname{tw}(e_2,e_3)=1$ hold for it. We prove that it has a circular minimal realization. We let $l_1$ and $l_2$ denote the straight lines containing the boundary vertices of $T$ such that there are seven boundary vertices on $l_2$ ( $l_2$ is on the right in Figure 3). We draw a circle $\omega$ that contains all vertices of $T$ but the boundary vertices lying on $l_2$ in its interior (the dashed line in Figure 3). We regard the points of intersection of $\omega$ with boundary edges of $T$ as new boundary vertices. Extending the boundary edges of the tree $T$ with vertices on $l_1$ until they intersect $\omega$ and also regarding the resulting points of intersection with $\omega$ as new boundary vertices, we obtain a new tree $T'$ , which is planar equivalent to $T$ and all boundary vertices of which lie on $\omega$ . Thus, $T$ has indeed a circular minimal realization.

Figure 3

§ 4. Conclusions

The author looks forward to obtaining in the future a full classification of trees having circular minimal realizations by using the parquet techniques developed in [1], [2] and [6].



Bibliography

1.	A. O. Ivanov and A. A. Tuzhilin, Theory of extremal networks, Moscow–Izhevsk, Institute for Computer Studies, 2003, 424 pp. (Russian)
2.	A. O. Ivanov and A. A. Tuzhilin, Minimal networks. The Steiner problem and its generalizations, CRC Press, Boca Raton, FL, 1994, xviii+414 pp.
3.	M. R. Garey, R. L. Graham and D. S. Johnson, “The complexity of computing Steiner minimal trees”, SIAM J. Appl. Math., 32:4 (1977), 835–859
4.	A. O. Ivanov and A. A. Tuzhilin, “Geometry of minimal networks and the one-dimensional Plateau problem”, Russian Math. Surveys, 47:2 (1992), 59–131
5.	A. O. Ivanov and A. A. Tuzhilin, “The Steiner problem in the plane or in plane minimal nets”, Math. USSR-Sb., 74:2 (1993), 555–582
6.	A. O. Ivanov, I. V. Iskhakov and A. A. Tuzhilin, “Minimal trees for regular polygons: linear parquets realization”, Moscow Univ. Math. Bull., 48:6 (1993), 46–48
7.	A. O. Ivanov and A. A. Tuzhilin, “On minimal binary trees with a regular boundary”, Russian Math. Surveys, 51:1 (1996), 144–145
8.	A. A. Tuzhilin, “Complete classification of locally minimal binary trees with regular boundary. The case of skeletons”, Fundam. Prikl. Mat., 2:2 (1996), 511–562 (Russian)
9.	A. O. Ivanov and A. A. Tuzhilin, “Non-trivial example of a boundary set in generalized Steiner problem constructed with the help of computer geometry and visualization”, Computer Graphics & Geometry, 6:1 (2004), 75–99

Citation: I. N. Mikhailov, “Planar locally minimal trees with boundaries on a circle”, Sb. Math., 215:5 (2024), 658–666

Citation in format AMSBIB

\Bibitem{Mik24}

\by I.~N.~Mikhailov

\paper Planar locally minimal trees with boundaries on a~circle

\jour Sb. Math.

\yr 2024

\vol 215

\issue 5

\pages 658--666

\mathnet{http://mi.mathnet.ru/eng/sm10002}

\crossref{https://doi.org/10.4213/sm10002e}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4809225}

\zmath{https://zbmath.org/?q=an:07945689}

\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2024SbMat.215..658M}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001312960500004}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85204230165}

Linking options:

https://www.mathnet.ru/eng/sm10002

https://doi.org/10.4213/sm10002e

https://www.mathnet.ru/eng/sm/v215/i5/p96

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Statistics & downloads:
Abstract page:	288
Russian version PDF:	4
English version PDF:	15
Russian version HTML:	12
English version HTML:	98
References:	20
First page:	8

Что такое QR-код?

Registration to the website

Logotypes