# A Simple Derivation of the Gertsenshtein Effect

Andrea Palessandro<EMAIL_ADDRESS>Deloitte Consulting, Artificial
Intelligence and Data Tony Rothman<EMAIL_ADDRESS>New York University,
Department of Applied Physics (retired)

###### Abstract

As shown by Gertsenshtein in 1961, an external magnetic field can catalyze the
mixing of graviton and photon states in a manner analogous to neutrino-flavor
oscillations. We first present a straightforward derivation of the mechanism
by a method based on unpublished notes of Freeman Dyson. We next extend his
method to include boundary conditions and retrieve the results of Boccaletti
et al. from 1970. We point out that, although the coupling between the
graviton and photon states is extremely weak, the large magnetic fields around
neutron stars $\sim 10^{14}$ G make the Gertsenshtein effect a plausible
source of gravitons. We also point out that axion-photon mixing, a subject of
active current research, is essentially the same process as the Gertsenshtein
effect, and so the general mechanism may be of broad astrophysical and
cosmological interest.

##  1 Introduction

In a classic 1961 paper [1], Mikhail Gertsenshtein demonstrated that
electromagnetic waves passing through an external magnetic field in curved
space could be transmuted into gravitational waves. The result was entirely
classical but in quantum mechanical language one can say that the external
field “catalyzes” a resonant mixing between photon and graviton states in a
manner analogous to the mixing of neutrino flavors. Although the coupling
between the graviton and photon states is extremely weak, the large magnetic
fields associated with, for example, neutron stars, make the Gertsenshtein
effect a plausible source for producing gravitons [2]. Zel’dovich [3],
however, and Dyson [4, 5] pointed out that the Gertsenshtein mechanism
requires coherence between the gravitational and electromagnetic waves. Large
magnetic fields create electron-positron pairs from the vacuum, which in turn
alters its index of refraction. The speed of electromagnetic wave propagation
is lowered relative to that of the gravitational wave and the Gertsenshtein
mechanism is quenched.

The Gertsenstein effect received some attention in the 1970s when Boccaletti
et al. [6] provided a comprehensive discussion and de Logi and Mikelson [7]
calculated the cross section for graviton-photon conversion. Cross sections
have also been computed by Long et al. [8], and the effect has been discussed
by Ejlli [9] as well as Jones and Singleton [10]. More recently, the mechanism
has been mentioned in the context of the primordial gravitational wave, or
graviton, background by Vagnozzi and Loeb [11] and various others [12, 13, 14,
15, 16]. Nevertheless, most physicists apparently remain unaware of the
Gertsenshtein effect, although current calculations of axion-photon conversion
employ a nearly identical formalism (see §4).

As it turns out, Freeman Dyson rediscovered the Gertsenshtein effect in 2005
[4], evidently unaware of the previous work. When informed that he was not
first, he chose not to publish his notes, but gave them to one of us (TR). As
Dyson’s derivation is simpler than the others we have seen and has remained
unpublished, we thought it worthwhile to make it available in some form. In
the following section of this paper we present Dyson’s approach, filling in
some steps and clarifying a few ambiguities. In §3 we make contact with
Boccaletti et al.’s results. It will be seen that Dyson’s method is much
simpler. Finally in §4 we point out the similarity to axion-photon conversion,
and conclude by indicating some possible applications of the Gertsenshtein
effect in the cosmological context.

##  2 Graviton-Photon Oscillations

Consider the propagation of electromagnetic and gravitational waves in a flat
spacetime. For the gravitational wave (GW), we assume as usual that it is
represented by a weak perturbation $h_{\mu\nu}({\bf x},t)\ll 1$ traveling on a
Minkowski background such that the full spacetime metric is

$g_{\mu\nu}=\eta_{\mu\nu}+h_{\mu\nu}\ \ ;\ \
g^{\mu\nu}=\eta^{\mu\nu}-h^{\mu\nu}\ \ ;\ \
h^{\mu\nu}\equiv\eta^{\alpha\mu}\eta^{\beta\mu}h_{\alpha\beta},$ (2.1)

where we take the flat-space metric to be $\eta_{\mu\nu}=(-1,1,1,1)$.

We carry out our calculations in the standard transverse-traceless (TT), or
Lorentz, gauge. If the wave is taken to be propagating in the $z$-direction,
then $h_{\mu\nu}=h_{\mu\nu}(z,t)$ and the transverse components of the field
are $h_{11}=-h_{22}$ and $h_{12}=h_{21}$, which represent the two independent
polarizations of the GW.111We use units in which $G=c=1$ and follow MTW [17]
conventions throughout. In particular, Greek indices $=0...3$ are spacetime
indices, while Latin indices are spatial indices $=1...3$. Repeated indices in
any position are summed.

In the Lorentz gauge, the linearized gravitational wave equation (see [17],
chap.18 and [18], chap.10) is

$\Box h_{\mu\nu}=-16\pi T_{\mu\nu},$ (2.2)

with $\Box\equiv\partial^{\mu}\partial_{\mu}$. We assume that the energy-
momentum tensor $T_{\mu\nu}$ consists entirely of the electromagnetic energy
of the system. In doing so, we ignore gravitational backreaction, which is a
good approximation as long as $h_{\mu\nu}\ll 1$. Therefore we have

$4\pi
T_{\mu\nu}=F_{\mu\alpha}F_{\nu}\,^{\alpha}-\frac{1}{4}g_{\mu\nu}F_{\alpha\beta}F^{\alpha\beta},$
(2.3)

where $F_{\mu\nu}\equiv\frac{\partial A_{\nu}}{\partial
x^{\mu}}-\frac{\partial A_{\mu}}{\partial x^{\nu}}$ is the usual
electromagnetic field tensor and $A_{\mu}=(-\phi,\textbf{A})$ is the vector
potential. In terms of the electric and magnetic fields, the Maxwell stress
tensor reads

$4\pi T_{ij}=-(E_{i}E_{j}+B_{i}B_{j})+\frac{1}{2}\delta_{ij}(\bf E\cdot
E+B\cdot B).$ (2.4)

With our conventions, $F_{ij}=A_{j,i}-A_{i,j}=\varepsilon_{ijk}B_{k}$ and
$F_{i0}=A_{0,i}-A_{i,0}\equiv-\partial_{i}\phi-\dot{A}_{i}=E_{i}$.222Because
$h_{11}=-h_{22}$, we must also have $T_{11}=-T_{22}$, which is not generally
true for the stress tensor (2.4) unless $E_{3}=B_{3}=0$. This will be the case
for transverse electromagnetic waves traveling in the $z$-direction
(“radiation gauge”), which we also assume. (Here, $\varepsilon_{ijk}$ is the
usual permutation operator.)

We further assume that the electromagnetic wave obeys the vacuum Einstein-
Maxwell equations:

$\frac{1}{\sqrt{g}}(\sqrt{g}F^{\alpha\beta}),_{\beta}=0.$ (2.5)

Since with metric (2.1) the determinant is $g=1+{\cal O}(h_{ij}^{2})\approx
1$,(2.5) amounts to

$(g^{\alpha\mu}g^{\beta\nu}F_{\mu\nu}),_{\beta}=0.$ (2.6)

Working to first order in $h_{\mu\nu}$ we have

$\eta^{\alpha\mu}\eta^{\beta\nu}F_{\mu\nu},_{\beta}-\eta^{\alpha\mu}h^{\beta\nu}F_{\mu\nu},_{\beta}-\eta^{\alpha\mu}F_{\mu\nu}h^{\beta\nu},_{\beta}-\eta^{\beta\nu}h^{\alpha\mu}F_{\mu\nu},_{\beta}-\eta^{\beta\nu}F_{\mu\nu}h^{\alpha\mu},_{\beta}=0.$
(2.7)

However, in the Lorentz gauge $h^{\beta\nu},_{\beta}\equiv 0$, so the third
term vanishes. Discarding the second and fourth terms as small, but keeping
the final term as potentially large leaves

$\eta^{\alpha\mu}\eta^{\beta\nu}F_{\mu\nu},_{\beta}-\eta^{\beta\nu}h^{\alpha\mu},_{\beta}F_{\mu\nu}=0.$
(2.8)

For $\alpha=0$ (2.8) gives merely ${\bf\nabla\cdot E}=0$, as in flat space.
For $\alpha=i$, the equation becomes

$-\dot{E}_{i}+\varepsilon_{ik\ell}B_{\ell},_{k}+\dot{h}_{ij}E_{j}-h_{ij},_{k}\varepsilon_{jk\ell}B_{\ell}=0.$
(2.9)

(Since $h^{ij}=h_{ij}$, it is immaterial whether one writes this equation with
indices up or down.) The $\dot{E}_{i}$ term can be eliminated as in freshman
physics to get a wave equation for $B$. Taking the curl of (2.9) yields

$-\varepsilon_{rpi}\dot{E}_{i},_{p}+\varepsilon_{rpi}\varepsilon_{ik\ell}B_{\ell},_{kp}+\varepsilon_{rpi}({\dot{h}_{ij}E_{j}),_{p}-\varepsilon_{rpi}\varepsilon_{jk\ell}(h_{ij},_{k}B_{\ell}}),_{p}=0.$
(2.10)

By virtue of the homogeneous Maxwell equation $\bf\nabla\times E=-\dot{B},$
which is the same as in flat space, the first term is
$\partial^{2}B_{r}/\partial t^{2}\equiv B_{r,tt}$. By virtue of the
homogeneous Maxwell equation $\bf\nabla\cdot B=0$, the second term is
$\curl\curl\textbf{B}=-\nabla^{2}\textbf{B}\equiv-B_{r,\ell\ell}$.333Here we
have used the vector identity
$\curl\curl\textbf{A}=\nabla(\nabla\cdot\textbf{A})-\nabla^{2}\textbf{A}$

Next, we assume that the electric field $\bf E$ is entirely that of the
electromagnetic wave, but that the magnetic field consists of the field $\bf
b$ of the electromagnetic wave plus a background field ${\bf B}_{0}$, such
that ${\bf B=B}_{0}+{\bf b}$ with ${\bf B}_{0}\gg\bf b$; ${\bf B}_{0}\gg\bf
E$. Thus we can ignore the third term above as second-order small and (2.10)
becomes

$B_{r},_{tt}-B_{r},_{\ell\ell}-\varepsilon_{rpi}\varepsilon_{jk\ell}(h_{ij},_{k}B_{\ell}),_{p}=0.$
(2.11)

With the same assumptions as above and discarding terms $\sim b^{2}$, the
gravitational wave equation (2.2) becomes

$\Box
h_{ij}=4[B_{0i}B_{0j}+B_{0i}b_{j}+b_{i}B_{0j}-\frac{1}{2}\delta_{ij}(B_{0i}^{2}+2B_{0k}b_{k})].$
(2.12)

The trick is, first, to choose ${\bf B}_{0}=\text{constant}$,444Note that for
$i=j=3$, (2.12) gives $\Box h_{33}\sim\textbf{B}_{0}^{2}\neq 0$. This entails
the appearance of a longitudinal component of the gravitational wave $h_{33}$,
induced by $T_{33}$. Given that in our case $\Box h_{33}\sim{\bf
B}_{0}^{2}=\text{constant}$, this mode does not mix with the other two
transverse components; therefore, for the purpose of our derivation, we can
effectively ignore it. which linearizes both (2.11) and (2.12), and secondly,
to choose ${\bf B}_{0}$ at right angles to $\bf b$, which ensures a nonzero
coupling for the $h_{12}$ mode in (2.12). Assuming that the electromagnetic
wave is traveling in the $z$-direction, we take ${\bf b=b}_{y}(z,t)$ and ${\bf
B}_{0}\equiv{\bf B}_{0x}$. Then from (2.11):

$\ddot{b}_{y}-b_{y}^{\prime\prime}=h_{12}^{\prime\prime}B_{0},$ (2.13)

where the prime (′) indicates differentiation with respect to $z$, and from
(2.12):

$\ddot{h}_{12}-h_{12}^{\prime\prime}=-4B_{0}b_{y}.$ (2.14)

Note that the background field ${\bf B}_{0}$ makes the mixing between a vector
field (photon) and a tensor field (graviton) possible by providing the missing
angular momentum. Given that $\Box h_{ij}\sim T_{ij}\sim
E_{i}E_{j}+B_{i}B_{j}$, for the given field configuration the only possible
linear mixing is between the $h_{12}$ component of the gravitational wave and
the $b$-field of the electromagnetic wave. There is no interaction with the
other polarization state $h_{11}$.555Another way to see this is to note that
the polarization tensors for the GW can be written as the dyadics ${\bf
e}_{+}=\bf\hat{i}\hat{i}-\hat{j}\hat{j}$ and ${\bf
e}_{\times}=\bf\hat{i}\hat{j}+\hat{j}\hat{i}$. Thus, ${\bf e}_{+}\cdot{\bf
B}_{0}\ ||\ {\bf B}_{0}$ and ${\bf e}_{+}\cdot{\bf b}\ ||\ {\bf b}$, so the
$h_{11}$ mode produces no interaction between ${\bf B}_{0}$ and ${\bf b}$,
whereas ${\bf e}_{\times}\cdot{\bf B}_{0}\ ||\ {\bf b}$ and ${\bf
e}_{\times}\cdot{\bf b}\ ||\ {\bf B}_{0}$, so the $h_{12}$ mode does allow
interaction between ${\bf B}_{0}$ and ${\bf b}$.

It remains now only to solve the two coupled equations (2.13) and (2.14). We
search for “wave packet” solutions $f$ the form $f(z,t)=f_{r}(z-t)f_{s}(z+t)$,
where $r$ stands for “rapid” and $s$ stands for “slow”. The Ur-example would
be

$\displaystyle f$ $\displaystyle=$
$\displaystyle\cos(k_{r}z-\omega_{r}t)\cos(k_{s}z+\omega_{s}t)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left[\cos((k_{r}+k_{s})z+(\omega_{s}-\omega_{r})t)+\cos((k_{r}-k_{s})z-(\omega_{r}+\omega_{s})t)\right],$

where $\omega_{r}\gg\omega_{s}$ and in our units
$k_{r}=\omega_{r}\,;k_{s}=\omega_{s}$. Such wave packets can thus be regarded
either as product functions consisting of a high and low frequency component
or as a coherent superposition of waves traveling in the same direction, which
can be expected to form beats as in elementary physics.

Dropping subscripts, we write $h=h_{r}(z-t)h_{s}(z+t)$ and
$b=b_{r}(z-t)b_{s}(z+t)$, where in our units $h_{r}^{\prime}=-\dot{h}_{r}$ and
$h_{s}^{\prime}=\dot{h}_{s}$, with similar expressions for $b_{r}$ and
$b_{s}$. Inserting the trial functions into (2.13) and (2.14) gives

$b^{\prime}_{r}b^{\prime}_{s}=-\frac{B_{0}}{4}(h^{\prime\prime}_{r}h_{s}+2h^{\prime}_{r}h^{\prime}_{s}+h_{r}h^{\prime\prime}_{s})\approx-\frac{B_{0}}{4}h^{\prime\prime}_{r}h_{s},$
(2.15)

and

$h^{\prime}_{r}h^{\prime}_{s}=B_{0}b_{r}b_{s}.$ (2.16)

In (2.15) we have approximated $h^{\prime\prime}$ as
$h_{r}^{\prime\prime}h_{s}$, since by assumption $h_{r}$ is rapidly varying
and $h_{s}$ is slowly varying.

The equations can now be solved by inspection. Pick

$h^{\prime}_{r}=\frac{\sqrt{B_{0}}}{a}b_{r}\ \ ;\ \
h^{\prime}_{s}=a\sqrt{B_{0}}b_{s}\ \ ;\ \
b^{\prime}_{s}=-\frac{B_{0}^{3/2}}{4a}h_{s},$ (2.17)

with $a$ an arbitrary constant. These choices satisfy (2.15) and (2.16). The
functions $b_{r}$ and $h_{r}$ which describe the shape of the wave-packets can
also be chosen arbitrarily and have no effect on the behavior of the functions
$b_{s}$ and $h_{s}$, which describe the slow oscillation of the packets
between photon and graviton states.

Letting $a=1/2$ gives

$h^{\prime}_{s}=\frac{1}{2}\sqrt{B_{0}}b_{s}\ \ ;\ \
b^{\prime}_{s}=-\frac{1}{2}B_{0}^{3/2}h_{s},$ (2.18)

which have solutions

$h_{s}={\cal A}\sin\left(\frac{z+t+\phi}{L}\right)\ \ ;\ \ b_{s}={\cal
A}\sqrt{B_{0}}\cos\left(\frac{z+t+\phi}{L}\right),$ (2.19)

provided that $L\equiv 2/B_{0}$. Notice also that

$h_{s}^{2}+\frac{b_{s}^{2}}{B_{0}}={\cal A}^{2}=\text{constant},$ (2.20)

which shows that the total energy remains constant as the packet oscillates
(see the appendix for details). The frequency of oscillation is given by the
magnitude of the magnetic field: $\omega_{s}\equiv L^{-1}=B_{0}/2$.

We have seen that a uniform classical magnetic field $\textbf{B}_{0}$
catalyzes a linear mixing of the gravitational and photon fields. A quantum of
the mixed field oscillates between photon and graviton states with a mixing
length $L$ independent of wavelength, namely

$L=\frac{2}{B_{0}},$ (2.21)

where $B_{0}$ is the component of the background field perpendicular to the
direction of propagation of the quantum. This means that if a single photon
travels a distance $D$ through the uniform field $B_{0}$, it will emerge as a
graviton with probability

$P=\sin^{2}(D/L).$ (2.22)

The quadratic dependence of $P$ on $D$ makes this process interesting as a
possible astrophysical source of gravitons.

In cgs units

$L=\frac{2c^{2}}{\sqrt{G}B_{0}}\approx
2\text{Mpc}\left(\frac{1\,\text{Gauss}}{B_{0}}\right).$ (2.23)

Around a magnetar, the field can be $\sim 10^{14}$ G, leading to a mixing
length of only $\sim 10^{6}$ km. From (2.22) above, an observer stationed
within the boundaries of such a field at a distance $D\gg L$ from the star
could in principle observe a significant periodic change of magnetar
luminosity on a timescale of seconds. More realistically, the extent of a
neutron star’s magnetic field is $\sim 10$ km. Beyond its field boundaries
oscillations cease (§3) and the brightness of the star is diminished by a
factor of $10^{-10}$ in the direction perpendicular to the magnetic field.
Conceivably, two observers could infer the presence of the Gertsenstein
mechanism by comparing photon fluxes in directions parallel and perpendicular
to the neutron star $B$-field. However, since the effect is classical, such an
observation would not constitute a direct detection of gravitons [2, 19, 20].

We also note that $10^{14}$ G is approximately the Schwinger limit, at which
one expects the electromagnetic field equations to become nonlinear and
electron-positron pairs to be created. Pair creation would in turn alter the
index of refraction of the vacuum and change the speed of light, destroying
the presumed coherence of the gravitational and electromagnetic waves. Hence,
for such strong fields one should do a more detailed calculation before
drawing definite conclusions.

##  3 Inclusion of Boundary Conditions

In the previous section we obtained a general solution for graviton-photon
oscillations. Boccaletti et al. [6] employed a more conventional equation-
solving method to obtain a solution in which conversion takes place within a
finite region, say for $0\leq z\leq D$. Such a scenario is probably more
relevant to graviton production in the vicinity of neutron stars, for example.

We now employ the Dyson approach to retrieve their results for photon-to-
graviton conversion in this situation.

We assume that the constant background magnetic field
$\textbf{B}_{0}\equiv\textbf{B}_{0x}$ is confined to the finite region $0\leq
z\leq D$ (region II), with a plane right-moving electromagnetic wave traveling
along the $z$-axis incident upon it. By the Gertsenshtein effect, the
electromagnetic wave produces a left-traveling gravitational wave in region I
($z<0$), and a right-traveling gravitational wave in region III ($z>D$).

In the region where the magnetic field is non-zero, the transverse component
of the gravitational wave $h_{12}$ is described by a wave packet of the
form666As we saw in §2, the function $h_{r}(z-t)$ can be chosen arbitrarily.
Here we make the simplifying assumption that
$h_{r}(z-t)\propto\sin(\omega_{r}(z-t))$.

$h_{s}(z+t)h_{r}(z-t)=\mathcal{A}\sin\left(\omega_{s}(z+t)\right)\sin\left(\omega_{r}(z-t)\right)$
(3.1)

where $\omega_{r}$ ($\omega_{s}\equiv L^{-1}$) is the frequency of the rapidly
(slowly) oscillating component of the metric, $\cal A$ is the maximum
amplitude of the wave, and for simplicity we have set the global phase
$\phi=0$ in (2.19).

The most general solution for the gravitational wave in region II is then a
superposition of wave packets of the form (3.1) and plane waves. Following
[6], we turn now to a complex formalism to describe these waves, with the
understanding that physical solutions are always given by the real part of
complex amplitudes.

Using this formalism, $h_{12}$ in region II is given by (the real part of)

$h_{12}^{II}(z,t)=ae^{i\omega_{r}(z-t)}+be^{-i\omega_{r}(z+t)}+\mathcal{A}e^{-i\omega_{s}(z+t)}e^{i\omega_{r}(z-t)}\quad\text{for}\quad
0\leq z\leq D.$ (3.2)

The first two terms represent right-traveling and left-traveling plane waves
respectively, while the third term is a superposition of wave
packets.777Specifically, the third term is a combination of the four
elementary wave packets $\cos(\omega_{s}(z+t))\cos(\omega_{r}(z-t))$,
$\cos(\omega_{s}(z+t))\sin(\omega_{r}(z-t))$,
$\sin(\omega_{s}(z+t))\cos(\omega_{r}(z-t))$, and
$\sin(\omega_{s}(z+t))\sin(\omega_{r}(z-t))$.

In both regions $z<0$ and $z>D$ where the background magnetic field is zero,
the wave equation for the metric is $\Box h_{12}=0$, and the corresponding
vacuum solutions are

$h_{12}^{\text{I}}(z,t)=ce^{-i\omega_{r}(z+t)}\quad\text{for}\quad z<0,$ (3.3)

and

$h_{12}^{\text{III}}(z,t)=de^{i\omega_{r}(z-t)}\quad\text{for}\quad z>D,$
(3.4)

describing a generic left-traveling ($z<0$) or right-traveling ($z>D$) plane
wave.

In order to determine the constant coefficients $(a,b,c,d)$ in terms of
$\mathcal{A}$ we impose the usual boundary conditions demanding continuity of
the functions and their derivatives at $z=0$ and $z=D$:

$\begin{split}h_{12}^{\text{I}}(0,t)=h_{12}^{\text{II}}(0,t),\\\
\partial_{z}h_{12}^{\text{I}}(0,t)=\partial_{z}h_{12}^{\text{II}}(0,t),\\\
h_{12}^{\text{II}}(D,t)=h_{12}^{\text{III}}(D,t),\\\
\partial_{z}h_{12}^{\text{II}}(D,t)=\partial_{z}h_{12}^{\text{III}}(D,t).\end{split}$
(3.5)

Or, in terms of the coefficients:

$\begin{split}c=a+b+\mathcal{A}e^{-i\omega_{s}t},\\\
c=b-a-\left(1-\frac{\omega_{s}}{\omega_{r}}\right)\mathcal{A}e^{-i\omega_{s}t},\\\
d=a+be^{-2i\omega_{r}D}+\mathcal{A}e^{-i\omega_{s}(D+t)},\\\
d=a-be^{-2i\omega_{r}D}+\mathcal{A}e^{-i\omega_{s}(D+t)}\left(1-\frac{\omega_{s}}{\omega_{r}}\right).\end{split}$
(3.6)

This is a system of four linear equations for five unknowns. In terms of
$\mathcal{A}$, coefficients $(a,b,c,d)$ are:

$\begin{split}a=-\mathcal{A}\left(1-\frac{\omega_{s}}{2\omega_{r}}\right)e^{-i\omega_{s}t},\\\
b=-\mathcal{A}\frac{\omega_{s}}{2\omega_{r}}e^{iD(2\omega_{r}-\omega_{s})}e^{-i\omega_{s}t},\\\
c=\mathcal{A}\frac{\omega_{s}}{2\omega_{r}}\left(1-e^{iD(2\omega_{r}-\omega_{s})}\right)e^{-i\omega_{s}t},\\\
d=-\mathcal{A}\left(1-\frac{\omega_{s}}{2\omega_{r}}\right)(1-e^{-iD\omega_{s}})e^{-i\omega_{s}t}.\end{split}$
(3.7)

The presence of the time-dependent factor $\exp(-i\omega_{s}t)$ means that the
coefficients in (3.7) are not truly constant. However, given our assumption
that $e^{-i\omega_{s}t}$ is slowly varying, to first approximation we can
consider them time-independent:

$\begin{split}a=-\mathcal{A}\left(1-\frac{\omega_{s}}{2\omega_{r}}\right),\\\
b=-\mathcal{A}\frac{\omega_{s}}{2\omega_{r}}e^{iD(2\omega_{r}-\omega_{s})},\\\
c=\mathcal{A}\frac{\omega_{s}}{2\omega_{r}}(1-e^{iD(2\omega_{r}-\omega_{s})}),\\\
d=-\mathcal{A}\left(1-\frac{\omega_{s}}{2\omega_{r}}\right)(1-e^{-iD\omega_{s}}).\end{split}$
(3.8)

One can easily check that the metric $h_{12}$ with the coefficients in (3.8)
satisfies the wave equation in all three regions (in our approximation) as
well as the boundary conditions in (3.5). Hence, the full solution for
$h_{12}(z,t)$ is

$\begin{split}h_{12}^{I}(z,t)=\mathcal{A}\frac{\omega_{s}}{2\omega_{r}}(1-e^{iD(2\omega_{r}-\omega_{s})})e^{-i\omega_{r}(z+t)},\\\
h_{12}^{II}(z,t)=-\mathcal{A}\left(1-\frac{\omega_{s}}{2\omega_{r}}\right)e^{i\omega_{r}(z-t)}-\mathcal{A}\frac{\omega_{s}}{2\omega_{r}}e^{iD(2\omega_{r}-\omega_{s})}e^{-i\omega_{r}(z+t)}\\\
+\mathcal{A}e^{-i\omega_{s}(z+t)}e^{i\omega_{r}(z-t)},\\\
h_{12}^{III}(z,t)=-\mathcal{A}\left(1-\frac{\omega_{s}}{2\omega_{r}}\right)(1-e^{-iD\omega_{s}})e^{i\omega_{r}(z-t)}.\end{split}$
(3.9)

We can similarly derive a solution for the electromagnetic wave. From equation
(2.17), $b_{r}=h_{r}^{\prime}/(2\sqrt{B_{0}})$ and
$b_{s}=2h_{s}^{\prime}/\sqrt{B_{0}}$. Given that
$h_{r}(z-t)=e^{i\omega_{r}(z-t)}$ and
$h_{s}(z+t)=\mathcal{A}e^{-i\omega_{s}(z+t)}$, we have
$b_{r}(z-t)=i\omega_{r}/(2\sqrt{B_{0}})e^{i\omega_{r}(z-t)}$ and
$b_{s}(z+t)=-2i\mathcal{A}\omega_{s}/\sqrt{B_{0}}e^{-i\omega_{s}(z+t)}$, so
the electromagnetic wave packet in region II is of the form

$b_{r}(z-t)b_{s}(z+t)=\frac{1}{2}\mathcal{A}\omega_{r}e^{-i\omega_{s}(z+t)}e^{i\omega_{r}(z-t)}.$
(3.10)

By assumption, the incident electromagnetic wave is right-moving in both
regions I and III. In addition, we need to include a produced left-moving
electromagnetic wave in region I, as well as a combination of right-moving and
left-moving plane waves in region II, as we did for the gravitational wave in
(3.2). Consequently, after imposing the relevant boundary conditions as in
(3.5) and disregarding the slowly oscillating term $\exp(-i\omega_{s}t)\approx
1$, the full solution for $b(z,t)$ is:

$\begin{split}b^{I}(z,t)=\mathcal{B}\omega_{r}e^{i\omega_{r}(z-t)}+\frac{1}{4}(1-e^{iD(2\omega_{r}-\omega_{s})})\mathcal{A}\omega_{s}e^{-i\omega_{r}(z+t)},\\\
b^{II}(z,t)=\left[\mathcal{B}-\frac{1}{2}\mathcal{A}\left(1-\frac{\omega_{s}}{2\omega_{r}}\right)\right]\omega_{r}e^{i\omega_{r}(z-t)}-\frac{1}{4}e^{iD(2\omega_{r}-\omega_{s})}\mathcal{A}\omega_{s}e^{-i\omega_{r}(z+t)}\\\
+\frac{1}{2}\mathcal{A}\omega_{r}e^{-i\omega_{s}(z+t)}e^{i\omega_{r}(z-t)},\\\
b^{III}(z,t)=\left[\mathcal{B}-\frac{1}{2}\mathcal{A}\left(1-\frac{\omega_{s}}{2\omega_{r}}\right)(1-e^{-iD\omega_{s}})\right]\omega_{r}e^{i\omega_{r}(z-t)},\end{split}$
(3.11)

where $\mathcal{B}$ is the incident electromagnetic wave amplitude. Thus far,
the coefficient $\mathcal{B}$ is undetermined because we have had to solve for
five coefficients but have only four boundary conditions. However, one can
easily check that the wave equation (2.14) for $h_{12}$ in region II is
consistent with the second of (3.11) only if $\mathcal{B}=\mathcal{A}/2$. One
can also check that the resulting expressions for $h_{12}$ and $b$ conserve
energy.

The solutions (3.9) and (3.11) describe the conversion of an electromagnetic
wave to a gravitational wave, catalyzed by the constant background magnetic
field $B_{0}$. In region II where $B_{0}\neq 0$, the electromagnetic and
gravitational amplitudes slowly oscillate between each other via the
conversion term $\exp(-i\omega_{s}(z+t))$. Outside, in regions I and III, the
oscillation stops and the wave packets propagate independently.

The solution of [6] is an approximation of ours for $\omega_{s}\ll\omega_{r}$.
In fact, to leading order in $\omega_{s}$, the gravitational wave solution in
(3.9) becomes

$\begin{split}h_{12}^{I}(z,t)=\mathcal{A}\frac{\omega_{s}}{2\omega_{r}}(1-e^{2iD\omega_{r}})e^{-i\omega_{r}(z+t)},\\\
h_{12}^{II}(z,t)=\mathcal{A}\frac{\omega_{s}}{2\omega_{r}}e^{i\omega_{r}(z-t)}-\mathcal{A}\frac{\omega_{s}}{2\omega_{r}}e^{2iD\omega_{r}}e^{-i\omega_{r}(z+t)}-i\omega_{s}z\mathcal{A}e^{i\omega_{r}(z-t)},\\\
h_{12}^{III}(z,t)=-iD\omega_{s}\mathcal{A}e^{i\omega_{r}(z-t)},\end{split}$
(3.12)

where we have used $e^{-i\omega_{s}z}\approx 1-i\omega_{s}z$ for small
$\omega_{s}$.

The coefficients of (3.12) are the same as in [6], given that the authors use
a convention in which the wave packet solution is given by $\lambda
z/(2i\omega_{r})\exp(i\omega_{r}(z-t))$, with
$\lambda=2\omega_{r}\omega_{s}\mathcal{A}$. In this approximation, the
amplitude of the gravitational wave in region I vanishes if the condition
$\exp(2iD\omega_{r})=1$ is satisfied, and the amplitude of the gravitational
wave in region III depends linearly upon the length and magnitude of the
static field.

Similarly, the approximate solution for the electromagnetic wave is, to
leading order in $\omega_{s}$,

$\begin{split}b^{I}(z,t)=\frac{1}{2}\mathcal{A}\omega_{r}e^{i\omega_{r}(z-t)}+\frac{1}{4}(1-e^{2iD\omega_{r}})\mathcal{A}\omega_{s}e^{-i\omega_{r}(z+t)},\\\
b^{II}(z,t)=\frac{1}{2}\mathcal{A}\omega_{r}e^{i\omega_{r}(z-t)}-\frac{1}{4}e^{2iD\omega_{r}}\mathcal{A}\omega_{s}e^{-i\omega_{r}(z+t)}-\frac{1}{2}i\mathcal{A}\omega_{r}\omega_{s}ze^{i\omega_{r}(z-t)},\\\
b^{III}(z,t)=\frac{1}{2}\left(1-iD\omega_{s}\right)\mathcal{A}\omega_{r}e^{i\omega_{r}(z-t)}.\end{split}$
(3.13)

If the condition $e^{2iD\omega_{r}}=1$ is satisfied, the back-propagating wave
amplitude vanishes and only the incident wave is left in region I. The
solution in this approximation describes an incident electromagnetic wave of
amplitude $\mathcal{A}$ and energy $\omega_{r}$ that propagates into region II
and slowly converts to a gravitational wave with a rate given by
$\omega_{s}\equiv L^{-1}$. When the wave enters region III, the incident
electromagnetic wave amplitude is effectively reduced by a factor of
$iD\omega_{s}$ while the gravitational wave amplitude is increased by that
same factor:

$\displaystyle\begin{split}&\text{EM}:\quad\mathcal{A}\rightarrow\mathcal{A}\left(1-i\frac{D}{L}\right),\\\
\ &\text{GW}:\quad 0\rightarrow-i\mathcal{A}\frac{D}{L}.\end{split}$ (3.14)

##  4 Axion-Photon Conversion

Quite generally the Lagrangian density for the interaction of gravitational
waves with matter is

${\cal L}=-\frac{1}{2}h_{\mu\nu}T^{\mu\nu},$ (4.1)

where in our problem $T^{\mu\nu}$ is given by (2.3) and (2.4).

Currently, there is a large interest in axion-photon conversion [21, 22, 23],
as axions are presently the leading candidates for dark matter. In a process
much like the Gertsenshtein mechanism, axions emerging from the sun can be
transformed into X-ray photons by a strong laboratory magnetic field and
subsequently detected by an X-ray telescope. Indeed, the axion-photon
interaction Lagrangian can be written as

${\cal L}=-\frac{g_{a\gamma}}{4}aF_{\mu\nu}\tilde{F}^{\mu\nu},$ (4.2)

where
$\tilde{F}^{\mu\nu}\equiv\frac{1}{2}\varepsilon^{\mu\nu\alpha\beta}F_{\alpha\beta}$
is the dual electromagnetic field tensor, $a$ is the axion amplitude and
$g_{a\gamma}$ is the axion-photon coupling constant.

In terms of the electric and magnetic fields, the above expression amounts to
${\cal L}=g_{a\gamma}\,a\,{\bf E\cdot B}$, which is essentially the same
Lagrangian as the one we have been using except that the external magnetic
field couples to the $E$-field of the photon rather than the $B$-field.

Not surprisingly, then, we can employ Dyson’s approach for axion-photon
mixing. In the high-energy limit in which one can ignore the mass of the
axion, and in the presence of a background magnetic field $B_{0}$, the coupled
equations for the axion $a$ and the E-field of the photon $e$ are analogous to
(2.13) and (2.14):

$\begin{split}\ddot{a}-a^{\prime\prime}=-4g_{a\gamma}B_{0}e\\\
\ddot{e}-e^{\prime\prime}=g_{a\gamma}a^{\prime\prime}B_{0},\end{split}$ (4.3)

and they admit oscillatory solutions with mixing length

$L=\frac{2}{g_{a\gamma}B_{0}},$ (4.4)

which agrees with the high-energy limit of [21]. As one can see, this is for
all intents and purposes the result of §2.

##  5 Conclusions

The Gertsenshtein effect describes the conversion of electromagnetic waves
into gravitational waves and vice-versa. Conversion is made possible by an
external magnetic field that provides the extra angular momentum necessary for
a spin-1 field to mix with a spin-2 field.

In this paper, we have presented a novel approach to deriving the
Gertsenshtein effect due to Freeman Dyson. The key step in his method is to
decompose the simultaneous solution of the linearized gravitational wave and
Einstein-Maxwell equations into rapidly and slowly oscillating components. The
rapidly oscillating component describes the “shape” of the electromagnetic and
gravitational wave packets, while the slowly oscillating component describes
the “beats” between the two fields, with the resulting oscillations having a
mixing length independent of wavelength.

In §3 we extended Dyson’s method to include boundary conditions and retrieved
the result of [6] as a special case of our solution. We then employed (§4) the
same method in the context of axion-photon conversion with essentially
identical results. Given the quadratic form of Lagrangians in general and the
similarity of the axion-photon Lagrangian to the gravitational interaction
Lagrangian in particular, we may conjecture that Gertshenstein-like mechanisms
which cause mixing among multiple fields are “universal” and have widespread
cosmological utility. Our approach can almost certainly be applied to any
scenario involving these mechanisms.

In future papers we plan to extend the effect to the (original) Yang-Mills
SU(2) field as well as consider the possibility that graviton-photon mixing in
the long-wavelength limit might generate something resembling a cosmological
constant.

Acknowledgement: Knowing that any expression of gratitude will fall far short,
TR would like to thank the late Freeman Dyson for forty years of friendship
and inspiration. Among his many acts of generosity, one of the minor ones was
to make available the notes on which this project was based.

##  Appendix A Conservation of Energy

In this appendix we demonstrate in detail the statement made in §2, that
energy is conserved during the oscillations between the electromagnetic and
gravitational fields.

Choosing for simplicity $h_{r}(z-t)=\sin(\omega_{r}(z-t))$ as the rapidly
oscillating component of the metric, and retaining factors of $G$, the
gravitational wave packet is given by

$h(z,t)=h_{s}(z+t)h_{r}(z-t)=\mathcal{A}\sin(\omega_{s}(z+t))\sin(\omega_{r}(z-t)),$
(A.1)

while, by virtue of (2.17), the electromagnetic wave packet is given by

$b(z,t)=b_{s}(z+t)b_{r}(z-t)=\frac{1}{2\sqrt{G}}\mathcal{A}\omega_{r}\cos(\omega_{s}(z+t))\cos(\omega_{r}(z-t)).$
(A.2)

Thus the slowly oscillating components are out of phase by $\pi/2$, but the
rapidly oscillating components are as well, and so the above equations do not
in fact produce beats. The reason is that (A.1) is not the physical
gravitational wave packet.

To see this, note that the energy density of the electromagnetic wave is

$\epsilon_{\text{EM}}=\frac{b^{2}}{8\pi}=\frac{1}{32\pi
G}\mathcal{A}^{2}\omega_{r}^{2}\cos^{2}(\omega_{s}(z+t))\cos^{2}(\omega_{r}(z-t)),$
(A.3)

while the energy density of the gravitational wave is

$\epsilon_{\text{GW}}=\frac{\dot{h}^{2}}{32\pi G}\approx\frac{1}{32\pi
G}\mathcal{A}^{2}\omega_{r}^{2}\sin^{2}(\omega_{s}(z+t))\cos^{2}(\omega_{r}(z-t)),$
(A.4)

where we have approximated
$\dot{h}\approx\mathcal{A}\omega_{r}\sin(\omega_{s}(z+t))\cos(\omega_{r}(z-t))$
given that by assumption $\omega_{s}\ll\omega_{r}$. Equations (A.3) and (A.4)
do describe coherent oscillations in the energy density of the two fields,
suggesting that we take for the physical solution of the gravitational wave
packet

$\tilde{h}\equiv\frac{\dot{h}}{2\sqrt{G}}=\frac{1}{2\sqrt{G}}\mathcal{A}\omega_{r}\sin(\omega_{s}(z+t))\cos(\omega_{r}(z-t)).$
(A.5)

Indeed, the wave packets (A.2) and (A.5) describe a right-traveling plane wave
of frequency $\omega_{r}$ that slowly oscillates between gravitational and
electromagnetic states with frequency $\omega_{s}$. Summing (A.3) and (A.4)
and averaging over time gives

$\langle\epsilon_{\text{EM}}+\epsilon_{\text{GW}}\rangle=\frac{1}{8\pi}\langle
b^{2}+\tilde{h}^{2}\rangle=\frac{\mathcal{A}^{2}\omega_{r}^{2}}{64\pi G},$
(A.6)

showing that the total energy of the system is conserved as the packet
oscillates.

## References

  * [1] M. E. Gertsenshtein, “Wave resonance of light and gravitational waves,” Zh. Eksp. Theor. Fiz. 41, 113-114 (1961); Soviet Physics JETP 14, 84-85 (1962).
  * [2] T. Rothman and S. Boughn, “Can gravitons be detected?” Foundations of Physics 36, 1801-1825 (2006).
  * [3] Ya. B. Zel’dovich,“Electromagnetic and gravitational waves in a stationary magnetic field,” Zh. Eksp. Theor. Fiz. 68 1311-1315 (1973).
  * [4] F. J. Dyson, “Photon-Graviton Oscillations” (unpublished).
  * [5] F. J. Dyson, “Do gravitons exist?” Talk given at Boston University, November 8, 2005.
  * [6] D. Boccaletti et al., “Conversion of Photons into Gravitons and Vice Versa in a Static Electromagnetic Field,” Nuovo Cim. 20 B, 129-146 (1970).
  * [7] W. K. De Logi and A. R. Mickelson, “Electrogravitational conversion cross sections in static electromagnetic fields,” Phys. Rev. D 16, 2915-2927 (1977).
  * [8] H. N. Long et al. “Electromagnetic-gravitational cross-sections in external electromagnetic fields,” Mod. Phys. Lett. A9, 3619-3628 (1994).
  * [9] D. Ejlli, “Mixing of gravitons with photons in primordial magnetic fields,” arXiv:1307.7883.
  * [10] P. Jones and D. Singleton, “Interaction Between Gravitational Radiation and Electromagnetic Radiation,” Int. J. Mod. Phys. D https://doi.org/10.1142/S0218271819300106.
  * [11] S. Vagnozzi and A. Loeb, “The Challenge of Ruling Out Inflation via the Primordial Graviton Background,” Astrophys. J. Lett. 939 (2022) no.2, L22
  * [12] A. Ringwald, J. Schütte-Engel and C. Tamarit, “Gravitational Waves as a Big Bang Thermometer,” JCAP 03 (2021), 054.
  * [13] V. Domcke and C. Garcia-Cely, “Potential of radio telescopes as high-frequency gravitational wave detectors,” Phys. Rev. Lett. 126 (2021) no.2, 021104.
  * [14] V. Domcke, C. Garcia-Cely and N. L. Rodd, “Novel Search for High-Frequency Gravitational Waves with Low-Mass Axion Haloscopes,” Phys. Rev. Lett. 129 (2022) no.4, 041101.
  * [15] N. Aggarwal, O. D. Aguiar, A. Bauswein, G. Cella, S. Clesse, A. M. Cruise, V. Domcke, D. G. Figueroa, A. Geraci and M. Goryachev, et al. “Challenges and opportunities of gravitational-wave searches at MHz to GHz frequencies,” Living Rev. Rel. 24 (2021) no.1, 4.
  * [16] A. Berlin, D. Blas, R. Tito D’Agnolo, S. A. R. Ellis, R. Harnik, Y. Kahn and J. Schütte-Engel, “Detecting high-frequency gravitational waves with microwave cavities,” Phys. Rev. D 105 (2022) no.11, 116011.
  * [17] C. Misner, K. Thorne and J. Wheeler, Gravitation, (W.H. Freeman, New York, 1973).
  * [18] S. Weinberg, Gravitation and Cosmology (John Wiley, New York, 1972).
  * [19] S. Boughn and T. Rothman, “Aspects of Graviton Detection: Graviton Emission and Absorption by Atomic Hydrogen,” Class.Quant.Grav. 23 5839-5852 (2006).
  * [20] A. Palessandro and M. S. Sloth, “Gravitational Absorption Lines,” Phys. Rev. D 101 (2020) no.4, 043504
  * [21] V. Anastassopoulos et al. “New CAST Limit on the Axion-Photon Interaction,” Nature Phys. 13 584-590 (2017).
  * [22] C. Adair et al. “Search for Dark Matter Axions with CAST-CAPP,” Nature Commun. 13 6180 (2022).
  * [23] J. Matthews et al. “How do Magnetic Field Models Affect Astrophysical Limits on Light Axion-like Particles? An X-ray Case Study with NGC 1275,” Ap. J., in press, arXiv:2202.08875.


# Upward Point Set Embeddings of Paths and Trees††thanks: This work was
initiated at the 7th Annual Workshop on Geometry and Graphs, March 10–15,
2019, at the Bellairs Research Institute of McGill University, Barbados. We
are grateful to the organizers and to the participants for a wonderful
workshop.

Elena Arseneva Email<EMAIL_ADDRESS>Partially supported by by RFBR,
project 20-01-00488. Saint Petersburg State University, Russia  Pilar Cano
Email<EMAIL_ADDRESS>Supported by the F.R.S.-FNRS under Grant no. MISU
F 6001 1. Université Libre de Bruxelles, Belgium  Linda Kleist Email:
<EMAIL_ADDRESS>Technische Universität Braunschweig, Germany  Tamara
Mchedlidze Email<EMAIL_ADDRESS>Karlsruhe Institute of Technology, Germany
Saeed Mehrabi Email<EMAIL_ADDRESS>Memorial University, St. John’s, Canada
Irene Parada Email<EMAIL_ADDRESS>TU Eindhoven, The Netherlands
Pavel Valtr<EMAIL_ADDRESS>Work supported by grant no. 19-17314J
of the Czech Science Foundation (GAČR). Department of Applied Mathematics,
Charles University, Czech Republic

###### Abstract

We study upward planar straight-line embeddings (UPSE) of directed trees on
given point sets. The given point set $S$ has size at least the number of
vertices in the tree. For the special case where the tree is a path $P$ we
show that: (a) If $S$ is one-sided convex, the number of UPSEs equals the
number of maximal monotone paths in $P$. (b) If $S$ is in general position and
$P$ is composed by three maximal monotone paths, where the middle path is
longer than the other two, then it always admits an UPSE on $S$. We show that
the decision problem of whether there exists an UPSE of a directed tree with
$n$ vertices on a fixed point set $S$ of $n$ points is NP-complete, by
relaxing the requirements of the previously known result which relied on the
presence of cycles in the graph, but instead fixing position of a single
vertex. Finally, by allowing extra points, we guarantee that each directed
caterpillar on $n$ vertices and with $k$ switches in its backbone admits an
UPSE on every set of $n2^{k-2}$ points.

##  1 Introduction

A classic result by Fary, Stein, Wagner [11, 15, 16], known as Fary’s theorem,
states that every planar graph has a crossing-free straight-line drawing.
Given a directed graph (called _digraph_ for short), it is natural to
represent the direction of the edges by an _upward_ drawing, i.e., every
directed edge is represented by a monotonically increasing curve. Clearly, it
is necessary for the digraph to be acyclic in order to allow for an upward
drawing.

In nice analogy to Fary’s theorem, if a planar digraph has an upward planar
drawing, then it also allows for an upward planar straight-line drawing [8].
In contrast, not every planar acyclic digraph has an upward planar drawing
[8]. Nevertheless, some classes of digraphs always allow for such drawings.
For instance, every directed tree has an upward planar straight-line drawing
[7, p. 212].

In this work, we study upward planar straight-line drawings of directed trees
on given point sets. An _upward planar straight-line embedding_ (UPSE, for
short) of a digraph $G=(V,E)$ on a point set $S$, where $|V|\leq|S|$, is an
injection from $V$ to $S$ such that the induced straight-line drawing is
planar (crossing-free) and upward, i.e., for the directed edge $uv\in E(G)$,
the point representing $u$ lies below the point representing $v$. As point-set
embeddings of planar undirected graphs [3, 4, 5, 6, 14], UPSEs have been an
active subject of research [1, 2, 12, 13]. In the following we review the
state of the art in relation to our problems.

Kaufmann et al. [12] showed that in case $|V|=|S|$ it is NP-complete to decide
whether an upward planar digraph admits an UPSE on a given point set. We note
that the upward planar digraph obtained in their reduction contains cycles in
its underlying undirected graph. The same authors gave polynomial-time
algorithm to decide if an upward planar digraph admits an UPSE on a convex
point set.

A digraph whose underlying undirected structure is a simple path is called
_oriented path_. For the class of oriented paths multiple partial results have
been provided, by either limiting the class of the point set, the class of
oriented paths, or by considering the case where $|S|>|V|$. In particular, by
limiting the class of point sets, Binucci et al. showed that every oriented
path admits an UPSE on every convex point set of the same size [2]. By
limiting the class of oriented paths, it has been shown that the following
subclasses of oriented paths always admit an UPSE on any general point set of
the same size:

  1. 1.

An oriented path with at most five switches111A vertex of a digraph which is
either a source or a sink is called _switch_. and at least two of its
sections222A section of an oriented path is a subpath that connects two
consecutive switches. having length333The _length_ of a path is the number of
vertices in it. two [1].

  2. 2.

An oriented path $P$ with three switches [2].

  3. 3.

An oriented path $P=(v_{1},\dots,v_{n})$, so that if its vertex $v_{i}$ is a
sink, then its vertex $v_{i+1}$ is a source [2].

  4. 4.

An oriented path $P$ such that its decomposition into maximal monotone paths
$P_{1},P_{2}\ldots,P_{r}$ satisfies that $|P_{i}|\geq\sum_{j>i}|P_{j}|$ for
every $i=1,2,\ldots,r-1$ [6].

Given these partial results, it is an intriguing open problem whether every
oriented path $P$ admits an UPSE on every general point set $S$ with
$|P|=|S|$. In contrast to this question, there exists a directed tree $T$ with
$n$ vertices and a set $S$ with $n$ points in convex position such that $T$
does not admit an UPSE on $S$ [2]. While restricting the class of trees to
directed caterpillars, Angelini et al. [1] have shown that an UPSE exists on
any convex point set.

The variant of the problem where the point set is larger than the oriented
path, was considered by Angelini et al. [1] and Mchedlidze [13]. They proved
that every oriented path $P$ with $n$ vertices and $k$ switches admits an UPSE
on every general point set with $n2^{k-2}$ points [1] or on $(n-1)^{2}+1$
points Mchedlidze [13], respectively.

### Our Contribution.

In this paper we continue the study of UPSE of digraphs. We tackle the
aforementioned open problem from multiple sides. Firstly, we show that the
problem of deciding whether a digraph on $n$ vertices admits an UPSE on a
given set of $n$ points remains NP-complete even for trees when one vertex
lies on a predefined point. (Section 5). This strengthens the previously known
NP-completeness result, where the underlying undirected structure contained
cycles [12]. Thus, even if it is still possible that every oriented path
admits an UPSE on every general point set, this new NP-completeness might
foreshadow that a proof for this fact will not lead to a polynomial time
construction algorithm. Secondly, we provide a new family of $n$-vertex
oriented paths that admit an UPSE on any general set of $n$ points (Section
3), extending the previous partial results [1, 2]. Thirdly, by aiming to
understand the degrees of freedom that one has while embedding an oriented
path on a point set, we show that the number of different UPSEs of an
$n$-vertex oriented path on a one-sided convex set of $n$ points is equal to
the number of sections the path contains (Section 2). Finally, as a side
result, we study the case where the point set is larger than the graph and
show that the upper bound $n2^{k-2}$ on the size of a general point set that
hosts every oriented path [1] can be extended to caterpillars (Section 4),
where $k$ is the number of switches in the caterpillar. The proof is largely
inspired by the corresponding proof for oriented paths. However, the result
itself opens a new line of investigations of providing upper bounds on the
size of general point sets that are sufficient for UPSE of families of
directed trees.

### Definitions.

A set of points is called _general_ , if no three of its points lie on the
same line and no two have the same $y$-coordinate. The _convex hull_ $H(S)$ of
a point set $S$ is the point set that can be obtained as a convex combination
of the points of $S$. We say that a point set is in _convex position_ , or is
a _convex point set_ , if none of its points lie in the convex hull of the
others. Given a general point set $S$, we denote the lowest and the highest
point of $S$ by $b(S)$ and $t(S)$, respectively. A subset of points of a
convex point set $S$ is called _consecutive_ if its points appear
consecutively as we traverse the convex hull of $S$. A convex point set $S$ is
called _one-sided_ if the points $b(S)$ and $t(S)$ are consecutive in it;
refer to Figure 1.

Let $\Gamma$ be an UPSE of a digraph $G=(V,E)$ on a point set $S$. For every
$v\in V$, $\Gamma(v)$ denotes the point of $S$ where vertex $v$ has been
mapped to by $\Gamma$. A _directed tree_ is a digraph, whose underlying graph
is a tree. A digraph, whose underlying graph is a simple path is called
_oriented path_. A _directed caterpillar_ is a directed tree in which the
removal of the vertices of degree 1 results in an oriented path: the
_backbone_. For an oriented path $(v_{1},v_{2},\dots,v_{n})$, we call
$v_{i}v_{i+1}$ a _forward_ (resp., _backward_) edge if it is oriented from
$v_{i}$ to $v_{i+1}$ (resp., from $v_{i+1}$ to $v_{i}$). A vertex of a digraph
with in-degree (resp., out-degree) equal to zero is called a _source_ (resp.,
_sink_). A vertex of a digraph which is either a source or a sink is called
_switch_. A subpath of an oriented path $P$ connecting two of its consecutive
switches is said to be _monotone_ and called a _section_ of $P$. A section is
_forward_ (resp., backward) if it consists of forward (resp., backward) edges.

##  2 Counting Embeddings of Paths on Convex Sets

In this section, we study the number of UPSEs that an $n$-vertex oriented path
has on a one-sided convex set of $n$ points. We show that this number is equal
to the number of sections in the oriented path. We start with the following

######  Lemma 1.

Let $P$ be an $n$-vertex oriented path with $v_{1}$ being one of its end-
vertices and let $S$ be a one-sided convex point set with $|S|=n$. For any two
different UPSEs $\Gamma_{1}$ and $\Gamma_{2}$ of $P$ on $S$, it holds that
$\Gamma_{1}(v_{1})\neq\Gamma_{2}(v_{1})$.

###### Proof.

Let $\\{p_{1},\dots,p_{n}\\}$ be the points of $S$ sorted by $y$-coordinate.
For the sake of contradiction, assume that there exist two different UPSEs
$\Gamma_{1}$ and $\Gamma_{2}$ of $P$ on $S$ with
$\Gamma_{1}(v_{1})=\Gamma_{2}(v_{1})$. Additionally, assume that the
considered counterexample is minimal, in the sense that for the vertex $v_{2}$
of $P$, adjacent to $v_{1}$, $\Gamma_{1}(v_{2})\neq\Gamma_{2}(v_{2})$. By [2,
Lemma 3], vertices $v_{1}$ and $v_{2}$ lie on consecutive points of $S$. We
assume that the edge $v_{1}v_{2}$ is a forward edge; the case when
$v_{1}v_{2}$ is a backward edge is symmetric. Conditions
$\Gamma_{1}(v_{1})=\Gamma_{2}(v_{1})$,
$\Gamma_{1}(v_{2})\neq\Gamma_{2}(v_{2})$, and the fact that $v_{1}$, $v_{2}$
lie on consecutive points of $S$, imply that
$\Gamma_{1}(v_{1})=\Gamma_{2}(v_{1})=p_{1}$, and $\Gamma_{i}(v_{2})=p_{n}$,
$\Gamma_{j}(v_{2})=p_{2}$, with $i,j\in\\{1,2\\}$. Embedding $\Gamma_{i}$ is
an UPSE of $P$ when the edge $v_{2}v_{3}$ is backward, while $\Gamma_{j}$ is
an UPSE of $P$ when the edge $v_{2}v_{3}$ is forward. We arrive to a
contradiction. ∎

We are now ready to prove the result of this section.

######  Theorem 1.

An $n$-vertex oriented path $P$ with $k$ sections has exactly $k$ UPSEs on a
one-sided convex set of $n$ points.

###### Proof.

We first show that $P$ has at least $k$ UPSEs. To do so, let
$P=(v_{1},\dots,v_{n})$ be an oriented path with $k$ sections and let $S$ be a
one-sided convex point set with points $\\{p_{1},\dots,p_{n}\\}$ ordered by
the increasing $y$-coordinate. Let $v_{l}$ be the switch of $P$ preceding
$v_{n}$. Thus, the subpath of $P$ between $v_{l}$ and $v_{n}$ is $P$’s last
section. Let denote the subpath of $P$ between $v_{1}$ and $v_{l}$ by
$P^{\prime}$. We prove the statement of the theorem by the following stronger
induction hypothesis: there are $k$ UPSEs of $P$ on $S$, such that one of them
maps $v_{n}$ to $p_{n}$ (resp., $p_{1}$) if the last section is forward
(resp., backward). The base case of $k=1$ is trivial. Assume that the $k$-th
section of $P$ is forward (resp., backward) and let
$S^{\prime}=\\{p_{1},\dots,p_{l}\\}$ (resp.,
$S^{\prime}=\\{p_{n-l+1},\ldots,p_{n}\\}$). By induction hypothesis, the path
$P^{\prime}$ has $k-1$ UPSEs on $S^{\prime}$, with one of them mapping $v_{l}$
to $p_{1}$ (resp., $p_{n}$). Let $\Gamma$ be one of them. Assume that
$\Gamma(v_{l})=p_{i}$, $p_{i}\in S^{\prime}$. We shift every vertex that has
been mapped to point $p_{j}$, $i<j\leq l$ (resp., $n-l+1\leq j<i$) by $n-l$
points up (resp., down); refer to Figure 1(a). We map the $k$-th section to
points $p_{i+1},\dots,p_{i+n-l}$ (resp., $p_{i}-1,\dots,p_{i-n+l}$). This
gives us $k-1$ UPSEs of $P$ on $S$.

Figure 1: (a–b) An illustration for the proof of Theorem 1, showing an
extension of an UPSE of $P^{\prime}$ (black) to an UPSE of $P$ (gray). In (a)
$v_{l}$ lies on a non-extreme point of $S^{\prime}$, while in (b) $v_{l}$ is
an extreme point of $S^{\prime}$. (c) Description of path $P$ presented in
Theorem 2.

Recall that, by induction hypothesis, $P^{\prime}$ has an UPSE
$\Gamma^{\prime}$ on $S^{\prime}$ that maps $v_{l}$ to $p_{1}$ (resp.,
$p_{n}$) on $S^{\prime}$, since its last section is backward (resp., forward).
Thus, we can also extend $\Gamma^{\prime}$ by mapping the $k$-th section to
points $p_{l+1},\ldots,p_{n}$ (resp., $p_{1},\dots,p_{n-l}$); refer to Figure
1(b). Hence, there exists a UPSE of $P$ that maps $v_{n}$ to $p_{n}$(resp.,
$p_{1}$) if the last section is forward (resp., backward). By Lemma 1, no two
of the constructed embedding of $P$ on $S$ are the same. Thus, $P$ has at
least $k$ UPSEs on $S$.

We now apply a counting argument to show that each oriented path with $k$
sections has exactly $k$ UPSEs on $S$. Note that the total number of possible
UPSEs of different directed paths of size $n$ on an $n$-point one-sided convex
point set is $n\cdot 2^{n-2}$. To see this, note that an UPSE can be encoded
by the start point and the position (clockwise or counterclockwise
consecutive) of the next point. For the last choice the clockwise and the
counterclockwise choices coincide. Moreover, the number of oriented paths with
$n-1$ edges and $k$ sections is $\rho_{k}:=2\binom{n-2}{k-1}$ and the number
of $n$-vertex oriented paths is $\sum_{k=1}^{n-1}\rho_{k}=2^{n-1}$. Let
$\eta_{k}$ denote the number of UPSEs of all oriented paths on $n$ vertices
with $k$ sections.

As shown above, an oriented path with $k$ sections has at least $k$ UPSEs on
$S$. By the symmetry of the binomial coefficient, it holds that
$\rho_{k}=\rho_{n-k}$. Therefore, the number of UPSEs of all oriented paths
with $k$ and $n-k$ sections evaluates to at least
$k\rho_{k}+(n-k)\rho_{n-k}=\frac{n}{2}(\rho_{k}+\rho_{n-k})$. This implies

$\displaystyle n2^{n-2}$
$\displaystyle=\sum_{k=1}^{n-1}\eta_{k}\geq\sum_{k=1}^{n-1}k\rho_{k}=\frac{n}{2}\cdot\sum_{k=1}^{n-1}\rho_{k}=\frac{n}{2}\cdot
2^{n-1}=n2^{n-2}.$

Consequently, each oriented path with $k$ sections has exactly $k$ UPSEs on
$S$. ∎

##  3 Embedding of Special Directed Paths

In this section we present a family of oriented paths that always admit an
UPSE on every general point set of the same size. For an illustration of paths
in this family, consider Figure 1(c).

######  Theorem 2.

Let $P$ be an oriented path with three sections $P_{1}=(u_{1},\dots,u_{a})$,
$P_{2}=(v_{1},\dots,v_{b})$ and $P_{3}=(w_{1},\dots,w_{c})$, where
$u_{a}=v_{1}$, $v_{b}=w_{1}$ and $b\geq a,c$. Then path $P$ admits an UPSE on
any general set $S$ of $n=a+b+c-2$ points.

###### Proof.

We assume that $P_{1}$ is forward, otherwise, we rename the vertices of $P$ by
reading it off from vertex $w_{c}$. Let $\ell$ denote the line through $t(S)$
and $b(S)$, and let $\ell^{-}$ (resp., $\ell^{+}$) be the halfplane on the
left (resp., on the right) when walking from $b(S)$ to $t(S)$ along $\ell$. We
assume that both $\ell^{-}$ and $\ell^{+}$ are closed, and hence
$|S\cap\ell^{+}|+|S\cap\ell^{-}|=a+b+c$. We now consider two cases.

Figure 2: An illustration of the proof of Theorem 2. (a) Embedding of $P$ in
Case 1. (b) Embedding of $P$ in Case 2. Point set $S_{2}$ lies in the red
convex polygon.

Case 1: $|S\cap\ell^{+}|\geq a+c$ or $|S\cap\ell^{-}|\geq a+c$. We consider
the case $|S\cap\ell^{-}|\geq a+c$ (refer to Figure 2(a), with
$|S\cap\ell^{+}|\geq a+c$ being symmetric. We rotate a left heading horizontal
ray $r$ emanating from $t(S)$ in counter-clockwise direction until it hits the
$a$-th point (including $t(S)$); we let $p$ denote this point and let $S_{1}$
denote the points swept by $r$. Notice that $b(S)\not\in S_{1}$ because
$|S\cap\ell^{-}|>a$. We embed $P_{1}$ on the points in $S_{1}$, by sorting
them by ascending $y$-coordinate.

From $|S\cap\ell^{-}|\geq a+c$ it follows that $|(S\setminus
S_{1})\cap\ell^{-}|\geq c$. Hence, we can embed $P_{3}$ on $S\cap\ell^{-}$. To
do so, we rotate around $b(S)$ a left-heading horizontal ray $r^{\prime}$ in
clockwise direction until it hits the $c$-th point of $(S\setminus
S_{1})\cap\ell^{-}$; denote these $c$ points by $S_{3}$ and let $p^{\prime}$
be the last point hit by $r^{\prime}$. We embed $P_{3}$ on the points of
$S_{3}$ by sorting them by ascending $y$-coordinate.

Let $S_{2}=(S\setminus(S_{1}\cup S_{3}))\cup\\{b(S),t(S)\\}$. Then, the
polygonal region determined by the horizontal lines through $t(S)$ and $b(S)$,
the line through $t(S)$ and $p$, the line through $b(S)$ and $p^{\prime}$, and
the vertical line through the rightmost point of $S_{2}$ is a convex region
that contains all points in $S_{2}$ and and has $t(s)$ (resp., $b(s)$) as its
topmost (resp., bottommost) vertex. Therefore, we can embed $P_{2}$ onto
$S_{2}$ by sorting them by descending $y$-coordinate. We observe that
$u_{a}=v_{1}$ and $v_{b}=w_{1}$ have been consistently embedded on $b(S)$ and
$t(S)$, respectively.

Case 2: $|S\cap\ell^{+}|\leq a+c$ and $|S\cap\ell^{-}|\leq a+c$. It follows
that $|S\cap\ell^{-}|\geq b\geq a$ and $|S\cap\ell^{+}|\geq b\geq c$; refer to
Figure 2(b). Since $|S\cap\ell^{-}|\geq a$, we can construct the set
$S_{1}\subset S\cap\ell^{-}$ similarly to Case 1, and embed $P_{1}$ on its
points. We then rotate a right-headed horizontal ray $r^{\prime}$ in counter-
clockwise direction around $b(S)$ until it hits the $c$-th point $p^{\prime}$
of $\ell^{+}$ and denote by $S_{3}$ the points swapped by $r^{\prime}$. Since
$|S\cap\ell^{+}|>c$, $t(S)\not\in S_{3}$. We embed $P_{3}$ onto $S_{3}$ by
sorting the points by ascending $y$-coordinate.

Finally, let $S_{2}=(S\setminus(S_{1}\cup S_{3}))\cup\\{b(S),t(S)\\}$. We note
that the polygonal region determined by the horizontal lines through $t(S)$
and $b(S)$, the line through $t(S)$ and $p$, and the line through $b(S)$ and
$p^{\prime}$ is a convex polygon that contains all points of $S_{2}$. Also
recall that $b(S)$ and $t(S)$ are respectively the bottommost and the topmost
points of $S_{2}$. Thus, we can embed $P_{2}$ onto the points in $S_{2}$ by
sorting them by descending $y$-coordinate. Note that $u_{a}=v_{1}$ and
$v_{b}=w_{1}$ have been consistently mapped to $t(S)$ and $b(S)$,
respectively. ∎

##  4 Embedding Caterpillars on Larger Point Sets

In this section, we provide an upper bound on the number of points that
suffice to construct an UPSE of an $n$-vertex caterpillar. We first introduce
some necessary notation. Let $C$ be a directed caterpillar with $n$ vertices,
$r$ of which, $v_{1},v_{2},\dots,v_{r}$, form its backbone. For each vertex
$v_{i}$ ($i=1,2,\dots,r$), we denote by $A(v_{i})$ (resp., $B(v_{i})$) the set
of degree-one vertices of $C$ adjacent to $v_{i}$ by outgoing (resp.,
incoming) edges. Moreover, we let $a_{i}=|A(v_{i})|$ and $b_{i}=|B(v_{i})|$.

######  Theorem 3.

Let $C$ be a directed caterpillar with $n$ vertices and $k$ switches in its
backbone. Then $C$ admits an UPSE on any general point set $S$ with $|S|\geq
n2^{k-2}$.

###### Proof.

Assume that $C$ contains $r$ vertices $v_{1},v_{2},\dots,v_{r}$ in its
backbone. Let $C_{\alpha,\beta}$ denote the subgraph of $C$ induced by the
vertices $\bigcup_{i=\alpha}^{\beta}{\\{v_{i}\\}\cup A(v_{i})\cup B(v_{i})}$.
We first make the following observation.

######  Observation 1.

If the backbone of $C$ contains exactly one section, $C$ has an UPSE on any
general set $S$ of $n$ points.

To see that, we sort the points in $S=\\{p_{1},\dots,p_{n}\\}$ by ascending
$y$-coordinate and, assuming $C$ is forward (the backward case is symmetric),
we embed $v_{i}$ on $p_{x}$, where $x=i+b_{i}+\sum_{j=1}^{i-1}(b_{j}+a_{j})$.
See to Figure 3(a) for an illustration.

Figure 3: Illustration of the proofs of (a) Observation 1; (b) Theorem 3.

We now prove the theorem by induction on $k$. We assume as the induction
hypothesis that a directed caterpillar $C$ with $i$ switches and $n_{i}$
vertices has an UPSE on any general point set $S$ of at least $n_{i}2^{i-2}$
points. Let $v$ denote the first vertex of the backbone of $C$. We
additionally assume that if $v$ is a source (resp. sink), then $v$ is mapped
on the $(|B(v)|+1)$-th bottommost (resp. $(|A(v)|+1)$-th topmost) point of
$S$. For $k=2$, the backbone of $C$ contains one section; hence, the induction
hypothesis follows from Observation 1 and its proof.

We now consider a caterpillar $C$ with $i+1$ switches and $n_{i+1}$ vertices.
Let $v_{1}$ and $v_{l}$ denote the first and the second switches of the
backbone of $C$, respectively. Let $S$ be a set of at least $N=n_{i+1}2^{i-1}$
points. In the following, we only consider the case where the backbone of
$C_{1,l}$ is forward; the backward case is symmetric.

We construct an UPSE of $C_{1,l-1}$ on the
$c_{1}=\sum_{i=1}^{l-1}{(1+b_{i}+a_{i})}$ lowest points of $S$ by applying
Observation 1. Let $p$ denote the point where $v_{l-1}$ is mapped. Let
$S^{\prime}$ denote the unused points of $S$; thus, $|S^{\prime}|=N-c_{1}$. We
have $n_{i+1}=n_{i}+c_{1}$, where $n_{i}$ is the number of vertices of
$C_{l,r}$. Recall that $N=n_{i+1}2^{i-1}$. Therefore,
$|S^{\prime}|>n_{i}2^{i-1}$. Let $p^{\prime}$ be the $(a_{l}+1)$-th topmost
point in $S^{\prime}$ and let $\ell$ denote the line through $p$ and
$p^{\prime}$. Line $\ell$ partitions $S^{\prime}$ into two sets, so that for
the largest, say $S^{\prime\prime}$, it holds that $|S^{\prime\prime}|\geq
n_{i}2^{i-2}$. Let $S^{\prime\prime\prime}$ be the union of $S^{\prime\prime}$
with the set of points lying above $v_{l}$. Since $C_{l,r}$ contains $i$
switches, by induction hypothesis, we can construct an UPSE of $C_{l,r}$ on
$S^{\prime\prime\prime}$ such that $v_{l}$ is mapped on the $(a_{l}+1)$-th
topmost point of $S^{\prime\prime\prime}$, which is the point $p^{\prime}$.
The only edge of the drawing of $C_{1,l}$ that interferes with the drawing of
$C_{l,r}$ is $(v_{l-1},v_{l})$; however, the drawing of $C_{l,r}$ (except for
the edges incident to $v_{l}$) lies on one side of the edge $(v_{l-1},v_{l})$.
See to Figure 3(b) for an illustration. ∎

##  5 NP-Completeness for Trees

In this section, we consider the following problem: Given a directed tree $T$
with $n$ vertices, a vertex $v$ of $T$, a set $S$ of $n$ points in the plane,
and a point $p$ in $S$, does $T$ have an UPSE on $S$ which maps $v$ to $p$?
Our goal is to show the following.

######  Theorem 4.

UPSE of a directed tree with one fixed vertex is $NP$-complete.

The 3-Partition problem is a strongly NP-complete problem by Garey and Johnson
[9, 10], which is formulated as follows: For a given multiset of $3m$ integers
$\\{a_{1},\ldots,a_{3m}\\}$, does there exist a partition into $m$ triples
$(a_{11},a_{21},a_{31}),\ldots,$ $(a_{1m},a_{2m},a_{3m})$, so that for each
$j\in[m]$, $\sum_{i=1}^{3}a_{ij}=b$, where $b=(\sum_{i=1}^{3m}a_{i})/m$. In
this section, we present a reduction from 3-Partition. Without loss of
generality, we may assume, possibly multiplying each $a_{i}$ by 3, that each
$a_{i}$ is divisible by 3.

Figure 4: An illustration of the tree $T$ in the proof of Theorem 4.

Given $3m$ integers $\\{a_{1},\ldots,a_{3m}\\}$, where each $a_{i}$ is
divisible by 3, we construct an instance of our problem as follows. Let $\ell$
and $h$ be two large numbers such that $\ell>mb$ and $h=m+1$. We construct a
tree $T$ with $n:=mb+h\ell+1$ vertices, and a point set $S$ with $n$ points.
As illustrated in Figure 4, (the undirected version of) the tree $T$ is a
subdivision of a star, that is, $T$ has a single vertex $s$ of degree greater
than two. Specifically, the degree of vertex $s$ is $3m+h$, i.e., $3m+h$ paths
meet in their initial vertex $s$; we call each such path a _branch_ of $T$.
Let $T_{1},\ldots,T_{3m+h}$ denote the branches, respectively. For
$i\in\\{1,\dots,3m\\}$, the branch $T_{i}$ is a path with $a_{i}$ edges and
called _small_ ; for $i\in\\{3m+1,\dots,3m+h\\}$, the branch $T_{i}$ is a path
with $\ell$ edges and called _large_. Note that $a_{i}$ and $\ell$ may also be
interpreted as the number of vertices of a branch that are different from $s$.

For each branch $T_{i}$, we define its _root_ $r_{i}$ as follows. For a small
branch $T_{i}$, $r_{i}$ is the first vertex on $T_{i}$ that is different from
$s$; for a large branch, $r_{i}$ is the second vertex different from $s$. For
every branch, all edges are oriented so that its root is the unique sink of
the branch. Thus the sinks of $T$ are exactly the $3m+h$ roots of the
branches, and the sources of $T$ are $s$ and the $3m+h$ leaves of $T$.

The point set $S$ is depicted in Figure 5 and constructed as follows. The
lowest point of $S$ is $p=(0,0)$. Let $E$ be an ellipse with center at $p$,
(horizontal) semi-major axis $5$ and (vertical) semi-minor axis $3$. Let $C$
be a convex $x$\- and $y$\- monotone curve above $E$ and also above the point
$(-3,3)$, represented by the filled square mark in Figure 5. Consider the cone
defined by the upward rays from $p$ with slopes -1, -2, and subdivide this
cone into $2m+1$ equal sectors by $2m$ upward rays from $p$.

Figure 5: An illustration of the point set $S$ in the proof of Theorem 4 and a
zoomed portion of $S$.

Let $s_{0},\ldots,s_{2m}$ denote the obtained sectors ordered counter-
clockwise. For each odd $i=2k+1$ with $0<i\leq 2m$, consider the intersection
between the sector $s_{i}$ and the ellipse $E$ (the orange arcs in Figure 5)
and let $B_{k}$ be the set of $b$ equally spaced points on this intersection.

For each even $i=2k$ with $0\leq k\leq m$, consider the intersection $c_{k}$
between sector $s_{i}$ and curve $C$ (the green arcs in Figure 5). Let the
point set $L_{k}$ be constructed as follows. Place the first point
$q_{k}^{\prime}$ of $L_{k}$ in the sector $s_{i}$ slightly to the right of
(and thus slightly below, to stay inside the sector) the topmost point of the
arc $c_{k}$. Let, for $k>0$, $x_{k}$ be the point of intersection between
$c_{k}$ and the line through $q_{k}^{\prime}$ and the topmost point of the set
$B_{k}$. For $k=0$ let $x_{k}$ be the highest point of $c_{k}$. Place the
second point $q_{k}$ of $L_{k}$ on $c_{k}$ slightly below $x_{k}$, but still
above $q_{k}^{\prime}$, see also Figure 5. Place $\ell-2$ points equally
spaced on $c_{k}$ below $q_{k}$. This concludes our description of $T$ and
$S$. In the remaining, the point sets $B_{k}$ are called _small sets_ , and
the point sets $L_{k}$ are called _large sets_.

To prove Theorem 4, we show that $\\{a_{1},\ldots a_{3m}\\}$ admits a
3-partition if and only if $T$ admits an UPSE $\Gamma$ on $S$ where
$\Gamma(s)=p$. In particular, our proof is based on the fact that if such an
UPSE exists, then it nearly fulfills the special property of being a
_consistent embedding_ of $T$ on $S$ (Lemma 2). An embedding $\Gamma$ is
_consistent_ if $\Gamma(s)=p$ and each large branch of $T$ is mapped to
exactly one large point set; for a schematic illustration consider Figure 6.

Figure 6: A schematic illustration of a consistent embedding of $T$ on $S$.

By construction of $S$, if the large branches are mapped to the large point
sets, then the small branches of $T$ must be subdivided into $m$ groups each
with a total of $b$ vertices. Each such group then corresponds to a triple
$(a_{1i},a_{2i},a_{3i})$ of the partition of $(a_{1},\ldots,a_{3m})$ that sums
up to $b$. Conversely, a 3-partition directly yields a consistent embedding.
This proves the following fact:

######  Observation 2.

$T$ has a consistent embedding on $S$ if and only if $\\{a_{1},\ldots
a_{3m}\\}$ has a 3-partition.

Now we prove the main lemma of this section in order to conclude Theorem 4.

######  Lemma 2.

If $T$ admits an UPSE $\Gamma$ on $S$ mapping $s$ to $p$ ($\Gamma(s)=p$), then
$T$ also admits a consistent UPSE on $S$ mapping $s$ to $p$.

###### Proof.

To show that $T$ admits a consistent embedding, we work our way from right to
left. Let $\Gamma_{i}$ denote the partial embedding of $T$ induced by
restricting $\Gamma$ to the points in $S_{i}:=\cup_{k\leq i}(L_{k}\cup B_{k})$
for every $i$. We say $\Gamma_{i}$ is consistent if large branches are mapped
to large sets of $S_{i}$ and small branches are mapped to small sets of
$S_{i}$. In particular, we prove the following: If there is an embedding
$\Gamma$ with $\Gamma(s)=p$ whose partial embedding $\Gamma_{i}$ is
consistent, then there is an embedding $\Gamma^{\prime}$ with
$\Gamma^{\prime}(s)=p$ whose partial embedding $\Gamma^{\prime}_{i+1}$ is
consistent.

For unifying notation, we define $B_{0},B_{-1},L_{-1}:=\emptyset$. Suppose
there is an embedding $\Gamma$ such that $\Gamma_{i}$ is consistent. Suppose
that the partial embedding $\Gamma_{i+1}$ of $\Gamma$ is not consistent
(otherwise let $\Gamma^{\prime}$ be $\Gamma$). Since $q_{i+1}$ is the highest
point of $S\setminus S_{i}$, $\Gamma(r_{j})=q_{i+1}$ for some branch $T_{j}$.
We distinguish two cases depending on whether $T_{j}$ is a small or large
branch. If $T_{j}$ is a small branch, then $B_{i+1}$ and $q_{i+1}^{\prime}$ is
to the right of segment $pq_{i+1}$. Depending on whether $T_{j}$ continues
left or right, a set of small branches is mapped on
$B_{i+1}\cup\\{q_{i+1}^{\prime}\\}$ or
$B_{i+1}\cup\\{q_{i+1},q_{i+1}^{\prime}\\}$, respectively. (In the latter
case, $T_{j}$ is one of the small branches mapped on
$B_{i+1}\cup\\{q_{i+1},q_{i+1}^{\prime}\\}$.) However, the cardinality of
these sets is not divisible by three; a contradiction. Therefore $T_{j}$ is a
large branch.

Then there exists a point $y\neq q_{i+1}^{\prime}$ such that the segments $py$
and $yq_{i+1}$ represent the first two edges of $T_{j}$. If $y$ belongs to a
large set, then $yq_{i+1}$ separates all points between $y$ and $q_{i+1}$ on
$C$ from $p$. Therefore, there are only three different options for the
placement of $y$ on a large set: $q_{i+2}$, $q^{\prime}_{i+2}$ or the left
neighbour of $q_{i+1}$ in $L_{i+1}$. If $y$ is $q_{i+2}$ or
$q^{\prime}_{i+2}$, then a number of small branches are mapped to
$B_{i+1}\cup\\{q^{\prime}_{i+2},q^{\prime}_{i+1}\\}$ or to
$B_{i+1}\cup\\{q^{\prime}_{i+1}\\}$, respectively. However, the cardinality of
these sets is not divisible by three, a contradiction. In the case that $y$ is
the left neighbour of $q_{i+1}$ in $L_{i+1}$, branch $T_{j}$ must continue to
the right of $q_{i+1}$. However, this would imply that $T_{j}$ contains at
most $b+3$ points, a contradiction to $\ell>b+3$. Therefore, $y$ belongs to a
small set $B_{j}$ with $j>i+1$. Moreover, $y$ belongs to $B_{i+2}$, otherwise
$q^{\prime}_{i+2}$ had to be the root of a large branch which would lead to a
contradiction. Let $A$ be the set of all points of $B_{i+2}$ to the right of
$y$. The set $A\cup\\{q_{i+1}^{\prime}\\}$ is separated from the rest of the
points of $S\setminus(S_{i}\cup\Gamma(T_{j})\cup B_{i+1})$ by the segments
$py$ and $yq_{i+1}$. Since there are less than $\ell$ points in
$A\cup\\{q^{\prime}_{i+1}\\}\cup B_{i+1}$, several small branches of $T$ are
mapped to $A\cup\\{q^{\prime}_{i+1}\\}\cup B_{i+1}$. In addition, since
$|B_{i+1}\cup\\{q_{i+1}^{\prime}\\}|$ is not divisible by three, for the small
branch that maps its root to $q^{\prime}_{i+1}$, the rest of this branch is
mapped to the left of $pq^{\prime}_{i+1}$. To construct a sought embedding
$\Gamma^{\prime}$ we modify $\Gamma$ as follows. Consider the point
$y^{\prime}$ in $B_{i+2}$ ($y^{\prime}$ lies to the right of $y$) such that
the segment $y^{\prime}q^{\prime}_{i+1}$ is in the partial embedding of
$\Gamma_{i+1}$. First, we map to $q_{i+1}^{\prime}$ the vertex of $T_{j}$
previously mapped to $y$ (i.e., $\Gamma^{-1}(y)$). Let $A^{\prime}\subset A$
be all the points to the left of $y^{\prime}$ in $A$. For each vertex mapped
to a point $z$ in $A^{\prime}\cup\\{y^{\prime}\\}$, we map such vertex to the
left neighbour of $z$ in $A^{\prime}\cup\\{y\\}$. Finally, the vertex that was
mapped to $q^{\prime}_{i+1}$ is now mapped to $y^{\prime}$. See Fig. 7.

Figure 7: (a) A partial embedding $\Gamma_{i+1}$ of $\Gamma$ that is not
consistent, while $\Gamma_{i}$ is. (b) A modification $\Gamma^{\prime}$ of
$\Gamma$ such that $\Gamma^{\prime}_{i+1}$ is consistent.

The obtained embedding $\Gamma^{\prime}$ is such that $\Gamma^{\prime}_{i+1}$
is consistent. Indeed, in $\Gamma^{\prime}$ the branch $T_{j}$ is embedded
entirely on $L_{i+1}$; otherwise some point of $L_{i+1}$ would be separated
from $p$. And since $|B_{i+1}|=b<\ell$, a set of small branches is embedded on
$B_{i+1}$. Together with the obvious fact that in any UPSE $\Gamma$ of $T$ on
$S$, $\Gamma_{-1}$ is consistent, the above observation implies the claim of
the lemma. ∎

##  6 Conclusion and Open Problems

In this paper, we continued the study of UPSE of directed graphs, specifically
of paths, caterpillars, and trees. On the positive side, we showed that a
certain family of $n$-vertex oriented paths admits an UPSE on any general
$n$-point set and that any caterpillar can be embedded on a general point set
if the set is large enough. Moreover, we provided the exact number of UPSEs
for every path on a one-sided convex set. On the negative side, we proved that
the problem of deciding whether a directed graph on $n$ vertices admits an
UPSE on a given set of $n$ points remains NP-complete even for trees when one
vertex lies on a pre-defined point. We conclude with a list of interesting
open problems:

  1. 1.

Given any oriented path $P$ and any general point set $S$ with $|P|=|S|$, does
there exist an UPSE of $P$ on $S$?

  2. 2.

If the answer to the previous question turns out to be negative, what is the
smallest constant $c$ such that a set of $c$ paths on a total of $n$ vertices,
has an UPSE on every general point set on $n$ points? This problem could also
be an interesting stepping stone towards a positive answer of the previous
question.

  3. 3.

Given a directed tree $T$ on $n$ vertices and a set $S$ of $n$ points, is it
NP-hard to decide whether $T$ has an UPSE on $S$?

  4. 4.

Can the provided upper bound on the size of general point sets that host every
caterpillar be improved to polynomial in the number of vertices, following the
result in [13]? If yes, can this be extended to general directed trees?

## References

  * [1] P. Angelini, F. Frati, M. Geyer, M. Kaufmann, T. Mchedlidze, and A. Symvonis.  Upward geometric graph embeddings into point sets.  In International Symposium on Graph Drawing (GD), volume 6502 of LNCS, pages 25–37. Springer, 2010.
  * [2] C. Binucci, E. D. Giacomo, W. Didimo, A. Estrella-Balderrama, F. Frati, S. G. Kobourov, and G. Liotta.  Upward straight-line embeddings of directed graphs into point sets.  Computational Geometry, 43:219–232, 2010.
  * [3] P. Bose.  On embedding an outer-planar graph in a point set.  Computational Geometry, 23(3):303–312, 2002.
  * [4] P. Bose, M. McAllister, and J. Snoeyink.  Optimal algorithms to embed trees in a point set.  Journal of Graph Algorithms and Applications, 1(2):1–15, 1997.
  * [5] S. Cabello.  Planar embeddability of the vertices of a graph using a fixed point set is NP-hard.  Journal of Graph Algorithms and Applications, 10(2):353–363, 2006\.
  * [6] O. Cagirici, L. Casuso, C. Medina, T. Patiño, M. Raggi, E. Roldán-Pensado, G. Salazar, and J. Urrutia.  On upward straight-line embeddings of oriented paths.  In Abs. of the XVII Spanish Meeting on Comput. Geom., pages 49–52, 2017.
  * [7] G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis.  Graph drawing: Algorithms for the visualization of graphs.  Prentice Hall, 1999.
  * [8] G. Di Battista and R. Tamassia.  Algorithms for plane representations of acyclic digraphs.  Theoretical Computer Science, 61(2-3):175–198, 1988.
  * [9] M. R. Garey and D. S. Johnson.  Complexity results for multiprocessor scheduling under resource constraints.  SIAM Journal on Computing, 4(4):397–411, 1975.
  * [10] M. R. Garey and D. S. Johnson.  Computers and intractability: A guide to the theory of NP-completeness.  W. H. Freeman & Co., 1979.
  * [11] F. István.  On straight-line representation of planar graphs.  Acta scientiarum mathematicarum, 11(229-233):2, 1948.
  * [12] M. Kaufmann, T. Mchedlidze, and A. Symvonis.  On upward point set embeddability.  Computational Geometry, 46(6):774–804, 2013.
  * [13] T. Mchedlidze.  Reprint of: Upward planar embedding of an n-vertex oriented path on ${O}(n^{2})$ points.  Computational Geometry, 47(3):493–498, 2014.
  * [14] J. Pach, P. Gritzmann, B. Mohar, and R. Pollack.  Embedding a planar triangulation with vertices at specified points.  Am. Math. Mon., 98:165–166, 1991.
  * [15] S. K. Stein.  Convex maps.  Proc. of the AMS, 2(3):464–466, 1951.
  * [16] K. Wagner.  Bemerkungen zum Vierfarbenproblem.  Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26–32, 1936.