11institutetext: Algorithms and Complexity Group, TU Wien (Vienna University
of Technology)
11email: {cbrand<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs

Cornelius Brand  0000-0002-1929-055X Robert Ganian  0000-0002-7762-8045
Sebastian Röder  Florian Schager

###### Abstract

In a right-angle crossing (RAC) drawing of a graph, each edge is represented
as a polyline and edge crossings must occur at an angle of exactly
$90^{\circ}$, where the number of bends on such polylines is typically
restricted in some way. While structural and topological properties of RAC
drawings have been the focus of extensive research, little was known about the
boundaries of tractability for computing such drawings. In this paper, we
initiate the study of RAC drawings from the viewpoint of parameterized
complexity. In particular, we establish that computing a RAC drawing of an
input graph $G$ with at most $b$ bends (or determining that none exists) is
fixed-parameter tractable parameterized by either the feedback edge number of
$G$, or $b$ plus the vertex cover number of $G$. AC drawings fixed-parameter
tractability vertex cover number feedback edge number

###### Keywords:

R

##  1 Introduction

Today we have access to a wealth of approaches and tools that can be used to
draw planar graphs, including, e.g., Fáry’s Theorem [29] which guarantees the
existence of a planar straight-line drawing for every planar graph and the
classical algorithm of Fraysseix, Pach and Pollack [28] that allows us to
obtain straight-line planar drawings on an integer grid of quadratic size.
However, much less is known about the kinds of drawings that can be achieved
for non-planar graphs. The study of combinatorial and algorithmic aspects of
such drawings lies at the heart of a research direction informally referred to
as “beyond planarity” (see, e.g., the relevant survey and book chapter [21,
18]).

An obvious goal when attempting to visualize non-planar graphs would be to
obtain a drawing which minimizes the total number of crossings. This question
is widely studied within the context of the crossing number of graphs, and
while obtaining such a drawing is NP-hard [33] it is known to be fixed-
parameter tractable when parameterized by the total number of crossings
required thanks to a seminal result of Grohe [34]. However, research over the
past twenty years has shown that drawings which minimize the total number of
crossings are not necessarily optimal in terms of human readability. Indeed,
the topological and geometric properties of such drawings may have a
significantly larger impact than the total number of crossings, as was
observed, e.g., by the initial informal experiment of Mutzel [41] and the
pioneering set of user experiments carried out by the graph drawing research
lab at the University of Sydney [36, 38, 37]. The latter works demonstrated
that “large-angle drawings” (where edge crossings have larger angles) are
significantly easier to read than drawings where crossings occur at acute
angles.

Motivated by these findings, in 2011 Didimo, Eades, and Liotta investigated
graph drawings where edge crossings are only permitted at $90^{\circ}$ angles
[20] (see Figure 1 for an illustration). Today, these _right-angle crossing_
(or _RAC_) drawings are among the best known and most widely studied beyond-
planar drawing styles [21, 18], with the bulk of the research to date focusing
on understanding necessary and sufficient conditions for the existence of such
drawings as well as the space they require [3, 4, 16, 17, 8, 1, 2, 27]. A
prominent theme in the context of RAC drawings concerns the number of times
edges are allowed to be bent: it has been shown that every graph admits a RAC
drawing if each edge can be bent $3$ times [20], and past works have
considered straight-line RAC drawings as well as RAC drawings where the number
of bends per edge is limited to $1$ or $2$.

(a) RAC drawing of $K_{5}$

(b) RAC drawing of $K_{3,3}$

Figure 1: Examples of RAC drawings.

And yet, in spite of the considerable body of work concentrating on
combinatorial and topological properties of such drawings, so far almost
nothing is known about the complexity of computing a RAC drawing of a given
graph. Indeed, while the problem of determining whether a graph admits a
straight-line RAC drawing is NP-hard [4] and was recently shown to be
$\exists\mathbb{R}$-complete [44], there is a surprising lack of known
algorithms that can compute such drawings for special classes of graphs or,
more generally, parameterized algorithms that exploit quantifiable properties
of the input graph to guarantee the tractability of computing RAC drawings
(either without or with limited bends). This gap in our understanding starkly
contrasts the situation for so-called $1$-planar drawings—another prominent
beyond-planar drawing style for which a number of fixed-parameter algorithms
are known [6, 25, 24]—as well as recent advances mapping the boundaries of
tractability for other graph drawing problems [35, 9, 10].

Contribution. We initiate an investigation of the parameterized complexity of
determining whether a graph $G$ admits a RAC drawing. Given the well-motivated
focus of previous works on limiting the amount of bends in such drawings, an
obvious first choice for a parameterization would be to consider an upper
bound $b$ on the total number of bends permitted in the drawing. However, on
its own such a parameter cannot suffice to achieve fixed-parameter
tractability in view of the NP-hardness of the problem for $b=0$, i.e., for
straight-line RAC drawings.

Hence, we turn towards identifying structural parameters of $G$ that guarantee
fixed-parameter RAC drawing algorithms. While established decompositional
parameters such as treewidth [43] and clique-width [14] represent natural
choices of parameterizations for purely combinatorial problems, the
applicability of these parameters in solving graph drawing problems is
complicated by the inherent difficulty of performing dynamic programming when
the task is to obtain a drawing of the graph. This is why the parameters often
used in this setting are non-decompositional, with the most notable examples
being the _vertex cover number_ $\mathbf{vcn}$ (i.e., the size of a minimum
vertex cover) and the _feedback edge number_ $\mathbf{fen}$ (i.e., the edge
deletion distance to acyclicity); further details are available in the
overview of related work below. As our main contributions, we provide two
novel parameterized algorithms:

  1. 1.

a fixed-parameter algorithm for determining whether $G$ admits a RAC drawing
with at most $b$ bends when parameterized by $\mathbf{fen}(G)$;

  2. 2.

a fixed-parameter algorithm for determining whether $G$ admits a RAC drawing
with at most $b$ bends when parameterized by $\mathbf{vcn}(G)+b$;

Both of the presented algorithms are constructive, meaning that they can also
output a RAC drawing of the graph if one exists. The core underlying technique
used in both proofs is that of _kernelization_ , which relies on defining
reduction rules that can provably reduce the size of the instance until it is
upper-bounded by a function of the parameter alone. While kernelization is a
well-established and generic technique, its use here requires non-trivial
insights into the structural properties of optimal solutions in order to
carefully identify parts of the graph which can be simplified without
impacting the final outcome.

We prove that both algorithms in fact hold for the more general case where
each edge is marked with an upper bound on the number of bends it can support,
allowing us to capture the previously studied $1$\- and $2$-bend RAC drawings.
Moreover, we show that the latter algorithm can be lifted to establish fixed-
parameter tractability when parameterized by $b$ plus the _neighborhood
diversity_ (i.e., the number of maximal modules) of $G$ [40, 30, 39]. In the
concluding remarks, we also discuss possible extensions towards more general
parameterizations and apparent obstacles on the way to such results.

Related Work. Didimo, Eades and Liotta initiated the study of RAC drawings by
analyzing the interplay between the number of bends per edge and the total
number of edges [20]. Follow-up works also considered extensions and variants
of the initial concept, such as upward RAC drawings [3], 2-layer RAC drawings
[16, 17] and 1-planar RAC drawings [8]. More recent works investigated the
existence of RAC drawings for bounded-degree graphs [2], and RAC drawings with
at most one bend per edge [1]. It is known that every graph admits a RAC
drawing with at most three bends per edge [20], and that determining whether a
graph admits a RAC drawing with zero bends per edge is NP-hard [4].

The vertex cover number has been used as a structural graph parameter to
tackle a range of difficult problems in graph drawing as well as other areas.
Fixed-parameter algorithms for drawing problems based on the vertex cover
number are known for, e.g., computing the obstacle number of a graph [5],
computing the stack and queue numbers of graphs [9, 10], computing the
crossing number of a graph [35] and 1-planarity testing [6]. Similarly, the
feedback edge number (sometimes called the _cyclomatic number_) has been used
to tackle problems which are not known to be tractable w.r.t. treewidth,
including 1-planarity testing [6] and the Edge Disjoint Paths problem [32]
(see also Table 1 in [31]).

These two parameterizations are incomparable: there are problems which remain
NP-hard on graphs of constant vertex cover number while being FPT when
parameterized by the feedback edge number (such as Edge Disjoint Paths [26,
32]), and vice-versa. That being said, the existence of a fixed-parameter
algorithm parameterized by the feedback edge number is open for a number of
graph drawing problems that are known to be FPT w.r.t. the vertex cover
number; examples include computing the aforementioned stack, queue and
obstacle numbers.

##  2 Preliminaries

We assume familiarity with standard concepts in graph theory [22]. All graphs
considered in this manuscript are assumed to be simple and undirected.

RAC Drawings. Given a graph $G=(V,E)$ on $n$ vertices with $m$ edges, a
_drawing_ of $G$ is a mapping $\delta$ that takes vertices $V$ to points in
the Euclidean plane $\mathbb{R}^{2}$, and assigns to every edge $e=uv\in E$
the image of a simple plane curve $[0,1]\rightarrow\mathbb{R}^{2}$ connecting
the points $\delta(u),\delta(v)$ corresponding to $u$ and $v$. We require that
$\delta$ is injective on $V$, and furthermore that for all vertices $v$ and
edges $e$ not incident to $v$, the point $\delta(v)$ is not contained in
$\mathrm{int}(\delta(e))$, where $\mathrm{int}(\delta(e))$ is the image of
$(0,1)$ under $\delta$.

A _polyline drawing_ of $G$ is a drawing such that for each edge $e\in E$,
$\delta(e)$ can be written as a union
$\delta(e)=\lambda^{e}_{1}\cup\cdots\cup\lambda^{e}_{t}$ of closed straight-
line segments $\lambda^{e}_{1},\ldots,\lambda^{e}_{t}$ such that:

  * •

for each $1\leq i\leq t-1$, the segments $\lambda^{e}_{i}$ and
$\lambda^{e}_{i+1}$ intersect in precisely one of their shared end-points and
moreover close an angle different than 180∘, and

  * •

every other pair of segments is disjoint.

The shared intersection points between consecutive segments are called the
_bends_ of $e$ in the drawing $\delta$.

For two edges $e$ and $f$, their set of _crossings_ in the drawing $\delta$ is
the set $\mathrm{int}(\delta(e))\cap\mathrm{int}(\delta(f))$. We will assume
without loss of generality that any drawing $\delta$ of $G$ has a finite
number of crossings.

The central type of drawing studied in this paper are those that allow only
_right-angle crossings_ between edge drawings (so-called _RAC drawings_): We
say that the edges $e,f\in E$ have a _right-angle crossing_ in a polyline
drawing $\delta$ of $G$ if the crossing lies in the relative interiors of the
respective line segments defining $\delta(e)$ and $\delta(f)$, and most
crucially, the intersecting line segments of $\delta(e)$ and $\delta(f)$ are
orthogonal to each other (i.e., they meet at a right angle). Let $\delta$ be a
polyline-drawing of a graph, $\beta:E\mapsto\\{0,1,2,3\\}$ a mapping, and
$b\in\mathbb{N}$ a number. If every crossing of $\delta$ is a right-angle
crossing, the number of bends counted over _all_ edges is at most $b$, and
every edge itself has at most $\beta(e)$ bends, $\delta$ is called a _$b$
-bend $\beta$-restricted RAC drawing_ of $G$. We note that

  * •

$0$-bend RAC drawings are straight-line RAC drawings (for any choice of
$\beta$),

  * •

$m$ and $2m$-bend drawings with $\beta(e)=1$ or $\beta(e)=2$ for each edge $e$
gives the usual notion of $1$-bend and $2$-bend RAC drawings, respectively,
and

  * •

similarly, $3m$-bend drawings with $\beta(e)=3$ for each edge $e$ gives rise
to the notion of $3$-bend RAC drawings, which exist for every graph [20].

Based on the above, we can now formally define our problem of interest:

Bend-Restricted RAC Drawing (BRAC)
Input: A graph $G$, an integer $b\geq 0$, and an edge-labelling
$\beta:E\mapsto\\{0,1,2,3\\}$. Question: Does $G$ admit a $b$-bend
$\beta$-restricted RAC drawing?

It has been shown that $b$-bend $\beta$-restricted RAC Drawing is
$\exists\mathbb{R}$-complete [44, 11] even when restricted to the case where
$b=0$. Without loss of generality, we will assume that the input graph $G$ is
connected. We remark that while BRAC is defined as a decision problem, every
algorithm provided in this paper is constructive and can output a drawing as a
witness for a yes-instance.

Parameterized Algorithms. We will not need a lot of the machinery of
parameterized algorithms to state our results. However, as it will turn out,
our tractability results all come under the guise of so-called _kernelization_
, which requires some context.

A _parameterized problem_ is an ordinary decision problem, where each instance
$I$ is additionally endowed with a _parameter_ $k$. Given such a parameterized
problem $\Pi$, we then say that a problem is _fixed-parameter tractable_ (FPT)
if there is an algorithm that, upon the input of an instance $(I,k)$ of $\Pi$,
decides whether or not $(I,k)$ is a yes-instance in time $f(k)\cdot
n^{\mathcal{O}(1)}$, where $f$ is any computable function, and $n=|I|$ is the
encoding length $|I|$ of the (parameter-free) instance $I$. This should be
contrasted with parameterized problems that require time, say, $n^{k}$ to
solve, which are not fixed-parameter tractable.

For instance, we may ask if a graph has a vertex-cover of size at most $k$,
and declare $k$ the parameter of the instance. In this case, the problem is
solvable in time $2^{k}\cdot n^{\mathcal{O}(1)}$, and hence FPT; in contrast,
asking for a dominating set of size $k$ (under some complexity assumptions)
requires time $n^{k}$ for every $k$. Closer to the problems treated in this
paper are structural parameterizations in the following sense: Suppose we are
given a graph $G$ and a number $k$ such that $G$ has a vertex-cover of size at
most $k$. Can we leverage this information to solve some (other) graph problem
at hand? In this case, we say that we parameterize the problem _by the vertex
cover number_.

When using such parameterizations in our results, we will crucially rely on
the following notion: A _kernelization_ (or kernel, for short) of $\Pi$ is a
polynomial-time algorithm (in $n$, and we may assume $k\leq n$ holds) that
takes an instance $(I,k)$ as input, and produces as output another instance
$(I^{\prime},k^{\prime})$ with the following properties: there is some
computable function $g$ such that both $k^{\prime}$ and $|I^{\prime}|$ are
bounded from above by $g(k)$, and $(I,k)$ is a yes-instance of $\Pi$ if and
only if $(I^{\prime},k^{\prime})$ is.

That is, a kernelization algorithms preprocesses instances of arbitrary size
into instances that are “parameter-sized,” and in particular (assuming $\Pi$
was decidable), this implies an algorithm running in time
$n^{\mathcal{O}(1)}+h(g(k))$ for some function $h$ (where $h(g(k))$ is the
running time of any algorithm solving instances of $\Pi$ of size $g(k)$). This
means in particular that $\Pi$ is fixed-parameter tractable (and, as a
standard result in parameterized algorithms, the converse of this claim holds
as well). We refer to the standard textbooks [23, 15] for a general treatment
of parameterized algorithms.

The _feedback edge number_ of a graph $G$, denoted $\mathbf{fen}(G)$, is the
size of a minimum edge set $F$ such that $G-F$ is acyclic. It is well-known
that such a set $F$ (and hence also the feedback edge number) can be computed
in linear time, since $G-F$ is a spanning tree of $F$. The _vertex cover
number_ of $G$, denoted $\mathbf{vcn}(G)$, is the size of a minimum vertex
cover of $G$, i.e., of a minimum set $X$ such that $G-X$ is edgeless. Such a
minimum set $X$ can be computed in time
$\mathcal{O}(1.2738^{|X|}+|X|\cdot|V(G)|)$ [13], and a vertex cover of size at
most $2|X|$ can be computed in linear time by a trivial approximation
algorithm. The third structural parameter considered here is the _neighborhood
diversity_ $\mathbf{nd}(G)$ of $G$, which is the minimum size of a partition
$\mathcal{P}$ of $V(G)$ such that for each $a,b$ in the same part of
$\mathcal{P}$ it holds that $N(a)\setminus\\{b\\}=N(b)\setminus\\{a\\}$. It is
well known that each part in such a partition $\mathcal{P}$ must be either a
clique or an independent set, and such a minimum partition can be computed in
polynomial time [40].

##  3 An Explicit Algorithm for BRAC

As already pointed out above, our results for fixed-parameter tractability
come as kernels. While there is a generic formal equivalence between the
existence of a kernel and a decidable problem being fixed-parameter tractable,
this doesn’t by itself yield explicit bounds on the running time of the
algorithm that results from this generic strategy. In order to derive concrete
upper bounds on the running time of our algorithms, we provide an algorithm
that solves _$b$ -bend $\beta$-restricted RAC drawing_ with a specific running
time bound. We do so via a combination of branching and an encoding in the
existential theory of the reals.

###### Theorem 3.1

An instance $(G,b,\beta)$ of BRAC can be solved in time
$m^{\mathcal{O}(m^{2})}$, where $m$ is the number of edges of $G$.

###### Proof

Observe that, without loss of generality, we may assume that $b\leq 3m$. We
begin by a branching step in which we exhaustively consider all possible
allocations of the bends to edges, resulting in a total number of at most
$4^{m}$ branches (some of which will be discarded due to exceeding the bound
$b$ or violating $\beta$). In each branch, we alter the graph $G$ by
subdividing each edge precisely the number of times it is assumed to be bent
in that branch. At this point, it remains to decide whether this new graph
$G^{\prime}$ admits a straight-line RAC drawing, where $G^{\prime}$ has
$\mathcal{O}(m)$ edges and vertices, and we denote these $m^{\prime}$ and
$n^{\prime}$, respectively.

To do this, one can construct a sentence in the existential theory of the
reals that is true if and only if $G^{\prime}$ admits such a drawing. The
variables of the sentence will consist of $n^{\prime}$ variable pairs
$(x_{v_{1}},y_{v_{1}}),\ldots,(x_{v_{n^{\prime}}},y_{v_{n^{\prime}}})$,
encoding the coordinates of the drawing of the vertices in $\mathbb{R}^{2}$.
Furthermore, for every pair of edges with endpoints $u,v$ and
$u^{\prime},v^{\prime}$, we can formulate a condition
$\sigma(u,v,u^{\prime},v^{\prime})\Rightarrow\tau(u,v,u^{\prime},v^{\prime})$,
where $\sigma$ is a polynomial condition in
$x_{u},x_{v},x_{u}^{\prime},x_{v}^{\prime}$ encoding whether the straight-line
segments corresponding to $uv$ and $u^{\prime}v^{\prime}$ intersect, and
$\tau$ is a polynomial condition in
$x_{u},x_{v},x_{u}^{\prime},x_{v}^{\prime}$ encoding whether these straight-
line segments are perpendicular. Indeed, the former requires an addition of
another $m^{\prime 2}$ auxiliary variables in the worst case, but both
conditions can be expressed by polynomials of degree two. This encoding is
described in full detail by Bieker [11].

To conclude the proof, we note that an existential sentence over the reals in
$N$ variables over $M$ polynomials of maximal degree $D$ can be decided in
time $(M\cdot D)^{\mathcal{O}(N)}$ (see, e.g., [7, Theorem 13.13]). Note that,
within essentially the same running time bound, one can also construct a
representation of a solution for this system [7, Theorem 13.11]. ∎

##  4 A Fixed-Parameter Algorithm via $\mathbf{fen}(G)$

We begin our investigation by establishing a kernel for Bend-Restricted RAC
Drawing when parameterized by the feedback edge number. Our kernel is based on
the exhaustive application of two reduction rules.

Let us assume we are given an instance $(G,b,\beta)$ of BRAC and that we have
already computed a minimum feedback edge set $F$ of $G$ in linear time. The
first reduction rule is trivial: we simply observe that vertices of degree one
can always be safely removed since they never hinder the existence of a RAC
drawing.

###### Observation 1

Let $v\in V(G)$ be a vertex with degree one. $G-\\{v\\}$ admits a $b$-bend
$\beta$-restricted RAC drawing if and only if $G$ does as well.

###### Proof

Clearly, if $G$ admits a $b$-bend $\beta$-restricted RAC drawing, then
$G-\\{v\\}$ does as well (one may simply remove $v$ and its incident edge from
the drawing). On the other hand, if $G-\\{v\\}$ admits a $b$-bend
$\beta$-restricted RAC drawing then we can extend this drawing to one for $G$
by placing $v$ sufficiently close to its only neighbor in a way which does not
induce any additional crossings. ∎

(a) Before removing degree-one vertices.

(b) After removing degree-one vertices.

Figure 2: Reduction rule one: Degree-one vertices can be pruned. Orange lines
represent feedback edges, dashed black lines represent long paths and special
vertices are marked in turquoise.

Iteratively applying the reduction rule provided by Observation 1 results in a
graph of the form $G^{\prime}=(V^{\prime},E^{\prime}\cup F)$, where
$T:=(V^{\prime},E^{\prime})$ is a tree with at most $2\cdot\mathbf{fen}(G)$
leaves and where each leaf of $T$ is incident to at least one edge in $F$. We
mark a vertex in $T$ as _special_ if it is an endpoint of an edge in $F$ or if
it has degree at least $3$ in $T$ (see Figure 2 for an illustration). Note
that the total number of special vertices is upper-bounded by
$4\cdot\mathbf{fen}(G)$: the total number of endpoints of edges in $F$ is
bounded by $2\cdot\mathbf{fen}(G)$, and since this also upper-bounds the
number of leaves this implies that there can be at most
$2\cdot\mathbf{fen}(G)$ vertices of degree at least $3$ in $T$.

In order to define the crucial second reduction rule, we will partition the
edges of $T$ into edge-disjoint paths such that each special vertex can only
appear as an endpoint in such paths.

###### Definition 1

We define the _path partition_ of $T$ in $G^{\prime}$ as the unique partition
$P_{1}\,\dot{\cup}\cdots\dot{\cup}\,P_{\ell}=E^{\prime}$ such that all $P_{i}$
are pairwise edge-disjoint paths in $T$ whose endpoints are both special
vertices, but with no special vertices in their interior. We call $\ell$ the
size of the path partition.

An illustration is provided in Figure 3. Given the established bound on the
number of special vertices, the size of the path partition is bounded by
$4\cdot\mathbf{fen}(G)$.

Figure 3: Path partition of $T$ with feedback edges in orange.

At this point, let us assume that we have a path partition
$P_{1}\,\dot{\cup}\,P_{2}\,\dot{\cup}\cdots\dot{\cup}\,P_{\ell}$ of $T$ in
$G^{\prime}$, where we index the paths in increasing order of length. Our next
task is to divide these paths into short and long paths by identifying whether
there exists a large gap in the lengths of these paths.

###### Definition 2

Define $p_{i}:=|P_{i}|$ for $i=1,\dots,\ell$, and moreover define $P_{0}:=F$
and $p_{0}:=|F|$. Let $i_{0}$ be the minimal $i=1,\dots,\ell$ such that
$p_{i}>9\ell\cdot p_{i-1}$, if one such $i$ exists, otherwise we set
$i_{0}:=\ell$. We call all paths $P_{i}$ with $1\leq i\leq i_{0}$ _short_ and
all other paths _long_. Then we define the subgraph $G_{\mathrm{short}}$ as
the edge-induced subgraph of $\bigcup_{i=0}^{i_{0}}P_{i}$ of $G^{\prime}$
(i.e., $G_{\mathrm{short}}$ arises by removing all long paths from
$G^{\prime}$).

Our aim is now to argue that if $\delta_{\mathrm{short}}$ is a RAC drawing of
$G_{\mathrm{short}}$, then we can always extend $\delta_{\mathrm{short}}$ to a
RAC drawing of $G^{\prime}$. Without loss of generality we assume that all
vertices in $V(G^{\prime})$ have already been drawn in
$\delta_{\mathrm{short}}$. First we create an intermediate drawing
$\delta^{\prime}$ of $G^{\prime}$, which will in general not be a RAC drawing.
We define $\delta^{\prime}$ as an extension of $\delta_{\mathrm{short}}$,
where each long path $P$ with endpoints $s$ and $t$ is represented as a simple
straight-line segment from $\delta_{\mathrm{short}}(s)$ to
$\delta_{\mathrm{short}}(t)$ with all interior vertices distributed
arbitrarily along that line segment. Doing this will in general violate the
RAC property of $\delta^{\prime}$, hence in the next step we need to alter
this straight-line segment in order to ensure that the drawing of $P$ crosses
only at right angles. For this we observe that any vertex on $P$ can be moved
to effectively act as a bend in a polyline drawing of $P$. We show that these
“additional bends” can be used to turn all crossings into right-angle
crossings.

###### Lemma 1

Let $P$ be a long path with endpoints $s$ and $t$ and consider its straight-
line representation $L$ in $\delta^{\prime}$. Assume $L$ intersects $k$
straight-line segments in $\delta^{\prime}$. Then, there exists a polyline
segment $L^{\star}$ from $\delta^{\prime}(s)$ to $\delta^{\prime}(t)$ with at
most $3k$ bends that intersects precisely the line segments intersected by
$L$, where each such segment is crossed precisely once and at a right angle.

###### Proof

For the purposes of this proof, it will be useful to treat each bend as an
auxiliary vertex in $\delta^{\prime}$ and treat straight-line segments as
edges. Let $e\in E(G_{\mathrm{short}})$ be an edge such that
$\delta^{\prime}(e)$ is crossed by $L$ at the point $x$. We now distinguish
the following cases of how $L$ intersects the straight-line segments in
$\delta^{\prime}$, and deal with each case separately:

  1. 1.

$x\in\mathrm{int}(\delta^{\prime}(e))$ and no other edge crosses through $x$.

  2. 2.

$\exists\,f\in E(G_{\mathrm{short}}):f\neq e\land
x\in\mathrm{int}(\delta^{\prime}(e))\cap\mathrm{int}(\delta^{\prime}(f))$.

  3. 3.

$\exists\,v\in V(G_{\mathrm{short}}):x=\delta^{\prime}(v)$.

We show how to deal with each of these three cases below:

  1. 1.

Let $\varepsilon>0$ such that
$B_{\varepsilon}(x)=\\{y\in\mathbb{R}^{2}:|x-y|<\varepsilon\\}$ contains no
vertices and intersects no other edges outside of $L$ apart from $e$. We
convert the intersection at $x$ to a right-angle crossing by introducing three
bends on the boundary $\partial B_{\varepsilon}(x)$ as illustrated in Figure
4: Put two vertices $v_{1}$, $v_{3}$ on the intersection of $L$ with $\partial
B_{\varepsilon}(x)$ to maintain the position of $L$ outside of
$B_{\varepsilon}(x)$. Construct the middle vertex $v_{2}$ by taking the
intersection of $\partial B_{\varepsilon}(x)$ with the normal line to $e$
going through $v_{3}$. Therefore we obtain our new polyline $L^{\star}$ by
joining the parts of $L$ outside the $\varepsilon$-neighborhood with the
polyline connecting the three vertices on the boundary of the
$\varepsilon$-neighborhood.

Figure 4: Dealing with a single crossing.

Since we chose $\varepsilon$ such that there are no further intersections
within this $\varepsilon$-neighborhood and the polyline remains unchanged
outside of this neighborhood, we are guaranteed to not introduce any new
crossings nor alter existing ones.

  2. 2.

Generalizing the first case, we now consider an intersection point $x$ with
multiple edges crossing it. We denote with $C=\\{e_{1},\dots,e_{t}\\}$ the set
of edges intersecting at $x$. Let $\varepsilon>0$ such that
$B_{\varepsilon}(x)$ contains no vertices and intersects no other edges apart
from the edges in $C$. Again, two entry and exit nodes $v_{1}$, $v_{t+1}$ are
added on the boundary of $B_{\varepsilon}(x)$ to preserve the original
position of $L$ outside of $B_{\varepsilon}(x)$. Assume the edges in $C$ are
ordered clockwise with $e_{1}$ being the closest edge to $v_{1}$. Now we
iteratively construct the next vertex $v_{i+1}$ by taking the intersection of
the angular bisector between $e_{i}$ and $e_{i+1}$ with the normal line to
$e_{i}$ going through $v_{i}$. If this point happens to lie outside of
$B_{\varepsilon}(x)$ we take the intersection of the normal line with
$\partial B_{\varepsilon}(x)$ instead. We refer to Figure 5 for an
illustration.

Figure 5: Crossing multiple edges at once.

In total, we need at most $t+1\leq 3t$ vertices.

  3. 3.

In the third case, the straight-line segment $L$ intersects with a vertex $v$
at $x=\delta^{\prime}(v)$. If $L\cap\delta^{\prime}(e)=\delta^{\prime}(v)$,
i.e. $L$ does not run parallel to $\delta^{\prime}(e)$, we can simply take
care of this equivalently as if $L$ would cross $\delta^{\prime}(e)$ in the
interior.

If otherwise $L\cap\delta^{\prime}(e)\supsetneq\delta^{\prime}(v)$, we observe
that $L$ must necessarily contain both endpoints of $\delta^{\prime}(e)$,
since the endpoints $\delta^{\prime}(s)$ and $\delta^{\prime}(t)$ of $L$
cannot lie in the interior of $\delta^{\prime}(e)$. At the first of these
endpoints encountered by $L$, say $w$, we again proceed analogously to the
second case (i.e., as if $w$ was a crossing point), however instead of exiting
the circle surrounding $w$ directly opposite to the entry point we exit at a
distance of $\varepsilon^{\prime}$ from there (for a sufficiently small
$\varepsilon^{\prime}$) and from there draw $L$ in parallel to $e$.

Since these three cases are exhaustive, the lemma follows. ∎

###### Lemma 2

Each long path intersects at most $3\ell\cdot p_{i_{0}}$ straight-line edge
segments in $\delta^{\prime}$.

###### Proof

Since each long path is represented as a straight-line segment in
$\delta^{\prime}$, it can cross every other long path at most once. Since
every edge $e\in E(G_{\mathrm{short}})$ can be bent at most $\beta(e)\leq 3$
times, $L$ can cross $e$ at most three times. Let $t$ be the number of long
paths, then $L$ intersects no more than

$t+3\sum_{i=0}^{i_{0}}p_{i}\leq t+3(\ell-t)\cdot p_{i_{0}}\leq 3\ell\cdot
p_{i_{0}}$

straight-line edge segments. ∎

###### Theorem 4.1

$b$-bend $\beta$-restricted RAC Drawing admits a kernel of size at most
$(36\cdot\mathbf{fen}(G))^{4\cdot\mathbf{fen}(G)}$. The kernel can be
constructed in linear time.

###### Proof

Consider an input $(G=(V,E),b,\beta)$ with feedback edge set $F$. In the first
step according to Observation 1 we iteratively prune all vertices of degree
one and obtain the reduced graph $G^{\prime}=(V^{\prime},E^{\prime}\cup F)$.
Next, we construct a path partition $\mathcal{P}=(P_{1},\dots,P_{\ell})$ of
the tree $T=(V^{\prime},E^{\prime})$ of size at most $4\cdot\mathbf{fen}(G)$.
Then we split the paths in $\mathcal{P}$ into short and long paths. We define
the subgraph $G_{\mathrm{short}}$ as the graph obtained by removing all long
paths from $G^{\prime}$ and show that it is a kernel.

(a) RAC drawing $\delta_{\mathrm{short}}$ of $G_{\mathrm{short}}$.

(b) RAC drawing $\delta$ of $G^{\prime}$

Figure 6: Extending the RAC drawing.

For that consider a RAC drawing $\delta_{\mathrm{short}}$ of
$G_{\mathrm{short}}$. We show that we can construct a RAC drawing $\delta$ of
$G^{\prime}$ that extends $\delta_{\mathrm{short}}$ (see Figure 6(b)). To
achieve this, we first define the intermediate drawing $\delta^{\prime}$,
which extends $\delta_{\mathrm{short}}$ by simply drawing all long paths as
straight-line segments. To obtain $\delta$ from $\delta^{\prime}$ we now
iteratively replace the straight-line representations by the polyline
constructions described in Lemma 1. Let $P_{i_{0}+1}$ be the first long path
with straight-line drawing $L_{i_{0}+1}$. According to Lemma 2 it is involved
in at most $3\ell\cdot p_{i_{0}}$ crossings in $\delta^{\prime}$. By the
definition of long paths we have $|P_{i_{0}+1}|>9\ell\cdot p_{i_{0}}$ and thus
we have enough vertices per crossing to construct $L_{i_{0}+1}^{*}$ via Lemma
1. Define $\delta_{i_{0}+1}$ by replacing $L_{i_{0}+1}$ with
$L_{i_{0}+1}^{\star}$ in $\delta^{\prime}$. Since $L_{i_{0}+1}^{\star}$ does
not introduce any new crossings, we can repeat this process for all further
long paths until we obtain $\delta:=\delta_{\ell}$ as our final RAC drawing of
$T$. Thus, we obtain $G_{\mathrm{short}}$ as a kernel of our original instance
with $b$ and $\beta$ unchanged, since we did not use any additional bends in
the construction of $\delta$.

Next, we show that $G_{\mathrm{short}}$ can be constructed in linear time. We
already observed that a Feedback Edge Set can be constructed in linear time.
Pruning vertices of degree one can be done in linear time as well, while the
task of finding a path partition of $T$ can be achieved by depth-first search
in linear time as well. Finally, the size of $G_{\mathrm{short}}$ can be
bounded by

$\displaystyle\sum_{i=0}^{i_{0}}p_{i}$
$\displaystyle\leq\sum_{i=0}^{\ell}p_{0}(9\ell\cdot\mathbf{fen}(G))^{i}$
$\displaystyle\leq 2\cdot\mathbf{fen}(G)(9\ell\cdot\mathbf{fen}(G))^{\ell}$
$\displaystyle\leq 2(36\cdot\mathbf{fen}(G))^{4\cdot\mathbf{fen}(G)}.$
$\square$

Using Theorem 4.1, the runtime guarantee given by Theorem 3.1 and the fact
that a feedback edge set of size $\mathbf{fen}(G)$ can be computed in linear
time, we obtain:

###### Corollary 1

$b$-bend $\beta$-restricted RAC Drawing is fixed-parameter tractable
parameterized by $\mathbf{fen}(G)$, and in particular can be solved in time
$2^{\mathbf{fen}(G)^{\mathcal{O}(\mathbf{fen}(G))}}+\mathcal{O}(|V(G)|)$.

###### Proof

After constructing the kernel in $\mathcal{O}(|V(G)|)$ time, we apply the
generic branching algorithm to the kernel with a runtime of

$\displaystyle((36\cdot\mathbf{fen}(G))^{4\cdot\mathbf{fen}(G)})^{\mathcal{O}\left((36\cdot\mathbf{fen}(G))^{8\cdot\mathbf{fen}(G)}\right)}$
$\displaystyle=(36\cdot\mathbf{fen}(G))^{\mathcal{O}\left((36\cdot\mathbf{fen}(G))^{8\cdot\mathbf{fen}(G)+1}\right)}$
$\displaystyle\leq
2^{(\log\mathbf{fen}(G))\cdot\mathbf{fen}(G)^{\mathcal{O}(\mathbf{fen}(G))}}$
$\displaystyle=2^{\mathbf{fen}(G)^{\mathcal{O}(\mathbf{fen}(G))},}$

which concludes the proof. ∎

##  5 Fixed-Parameter Tractability via $\mathbf{vcn}(G)$

As in Section 4, the core tool used to establish fixed-parameter tractability
for this parameterization is a kernelization procedure, although the ideas and
reduction rules used here are very different. Let us assume we are given an
instance $(G,b,\beta)$ of BRAC; as our first step, we compute a vertex cover
$C$ of size $k\leq 2\cdot\mathbf{vcn}(G)$ using the standard approximation
algorithm.

We now partition the vertices of our instance $G$ outside of the vertex cover
$C$ into _types_ , as follows. Two vertices in $G\setminus C$ are of the same
type if they have the same set of neighbors in $C$; observe that the property
of “being in the same type” is an equivalence relation, and when convenient we
also use the term _type_ to refer to the equivalence classes of this relation.
To avoid any confusion, we explicitly remark that two vertices may have the
same type even when their incident edges are assigned different values by
$\beta$. The number of types is upper-bounded by $2^{k}$.

We distinguish types by the number of neighbors in $C$; an illustration is
provided in Figure 7. Let a member of a type $T$ be defined as a vertex in $T$
as well as its incident edges. By an exhaustive application of the first
reduction rule introduced in Section 4 (cf. Observation 1), we may assume that
there is no type with less than $2$ neighbors in $C$.

Figure 7: A graph split into its vertex cover $C$ (in turquoise) and its
different types $T_{1},\dots,T_{4}$ (in orange).

Turning to types with at least $3$ neighbors in $C$, we provide a bound on the
size of each such type in a yes-instance of BRAC.

###### Lemma 3

If $(G,b,\beta)$ is a yes-instance of BRAC, then each type $T$ with $i\geq 3$
neighbors in $C$ has at most $\max(2,7-i)+b$ members.

###### Proof

Didimo, Eades and Liotta showed that no complete bipartite graph $K_{c,d}$
with $c+d>7$ and $\min(c,d)>2$ admits a straight-line RAC drawing [19]. Hence,
if vertices in $T$ have $3$ neighbors in $C$ then a $b$-bend
$\beta$-restricted RAC drawing of $G$ can contain at most $4$ members of $T$
without bends; otherwise, the drawing of $5$ members of $T$ and their $3$
neighbors in $C$ would contradict the first sentence. Similarly, if vertices
in $T$ have at least $5$ neighbors in $C$ then a $b$-bend $\beta$-restricted
RAC drawing of $G$ cannot contain $3$ members of $T$ without bends. ∎

Lemma 3 implies that we can immediately reject instances containing types with
more than $3$ neighbors whose cardinality is greater than $4+b$ (or, for the
purposes of kernelization, one may replace these with trivial no-instances).
Hence, it now remains to deal with types with precisely two neighbors in $C$.

We say that two edges $uv$ and $uv^{\prime}$ form a fan anchored at $u$. It is
easy to observe that if an edge $e$ crosses both $uv$ and $uv^{\prime}$ in a
$b$-bend $\beta$-restricted RAC drawing, then at least one of these three
edges must have a bend [3].

###### Lemma 4

Consider a $b$-bend $\beta$-restricted RAC drawing $\delta$ of $G$, and let
$T$ be a type containing vertices with precisely two neighbors in $C$. Let
$T^{\prime}$ be the subset of $T$ containing all members of $T$ which do not
have bends in $\delta$. Then $T^{\prime}$ contains at most four members
involved in crossings with other members of $T^{\prime}$ in $\delta$.

###### Proof

Let $u$ and $v$ be the neighbors of $T^{\prime}$ in the vertex cover $C$. Let
us consider the vertices lying on one side of the half plane induced by the
line $\overleftrightarrow{\delta(u)\delta(v)}$ going through $u$ and $v$.
According to Thales’s theorem, every right-angle crossing formed by two edges
originating in $u$ and $v$ respectively, has to lie on the semicircle with
diameter $\overline{\delta(u)\delta(v)}$. Suppose the edges $(u,x)$ and
$(v,w)$ cross at a right angle. Then there cannot be another edge incident to
$u$ which crosses the semicircle to the right of the first crossing .

Indeed, if there was such an edge $(u,y)$, then $(v,w)$ would cross the fan
formed by $(u,x)$ and $(u,y)$ as shown in Figure 8. Analogously, there also
cannot be an edge incident to $v$, which crosses the semicircle left to the
first crossing. Hence, there can be at most one right-angle crossing between
members of $T^{\prime}$ below and above
$\overleftrightarrow{\delta(u)\delta(v)}$, respectively. ∎

Figure 8: Illustration for Lemma 4.

Next, we use the above statement to obtain a bound on the total number of
crossings that such a type $T$ can be involved in. We do so by showing that
the members of $T$ which themselves do not have bends are only involved in a
bounded number of crossings.

###### Lemma 5

Consider a $b$-bend $\beta$-restricted RAC drawing $\delta$ of $G$, and let
$T$ be a type containing vertices with precisely two neighbors in $C$. Then at
most $3k+6+b$ members of $T$ can be involved in a crossing in $\delta$.

###### Proof

Let $T^{\prime}$ be the subset of $T$ containing all members of $T$ which do
not have bends in $\delta$, and let $\gamma=|T|-|T^{\prime}|$. Further, let
$T_{0}$ be the set of members of $T^{\prime}$ which are pairwise crossing
free, but which all cross at least some other edge in $\delta$. $T_{0}$ forms
a layering structure in $\delta$, as depicted in Figure 9. Moreover, if
$T_{0}$ contains two members that are incident to the same inner face in this
layering structure and whose edges are drawn in parallel in $\delta$, we
remove one of these members from $T_{0}$; observe that this may only reduce
the size of $T_{0}$ by one. Let $\alpha$ be the number of members that remain
in $T_{0}$ at this point.

At this point, an edge $e$ without any bends cannot cross more than one member
of $T_{0}$, as no two edges on the same face in $T_{0}$ are parallel by
assumption. Without bends, this would imply that there must be a vertex in
every layer, and since each vertex can only be connected to other vertices in
the same or in one of the two adjacent layers there can be at most $3k$
layers. Introducing bends, an edge outside $T^{\prime}$ might cross one
additional layer per bend; thus increasing the number of possibly crossed
members to $3k+1+b$. Since $\gamma$ bends are already used by edges of $T$, we
obtain $\alpha\leq 3k+1+b-\gamma$.

Moving our attention to $T^{\prime}\supseteq T_{0}$, the difference between
the sizes of these two sets can be caused (1) by up to 4 members that are
involved in crossings with other members of $T^{\prime}$ following Lemma 4 and
(2) by one additional member for the single removed member with parallel edges
from $T_{0}$, i.e. $|T^{\prime}|\leq\alpha+5$. Hence, at most
$\alpha+5+\gamma=3k+6+b$ members of $T$ can be involved in crossings in
$\delta$. ∎

Figure 9: Illustration for the proof of Lemma 5 with vertices in the vertex
cover marked in turquoise.

In particular, Lemma 5 implies that in a $b$-bend $\beta$-restricted RAC
drawing, every sufficiently large type $T$ with precisely $2$ neighbors in $C$
must contain a member that is not involved in any crossings. The next lemma
highlights why this is useful in the context of our kernelization.

###### Lemma 6

Let $T$ be a type with two neighbors in $C$ and assume that $G$ admits a
$b$-bend $\beta$-restricted RAC drawing $\delta$. If there is a member in $T$
whose edges are drawn without crossings in $\delta$, then the graph obtained
from $G$ by adding a vertex $w^{\prime}$ to $T$ admits a $b$-bend
$\beta$-restricted RAC drawing as well.

###### Proof

Let $u,v$ be the neighbors of $T$ in the vertex cover and let $w\in T$ be the
member without crossings. We can draw $w^{\prime}$ infinitesimally close to
$w$ such that the emerging layering triangles are drawn without crossings (see
Figure 10).

Figure 10: Illustration for the proof of Lemma 6.

∎

At this point, we have all the ingredients for the main result of this
section:

###### Theorem 5.1

$b$-bend $\beta$-restricted RAC Drawing admits a kernel of size
$\mathcal{O}(b\cdot 2^{k})$, where $k$ is the size of a provided vertex cover
of the input graph.

###### Proof

Consider an input $(G,b,\beta)$ and let $C$ be the provided vertex cover of
$G$. We apply the simple reduction rule of deleting vertices of degree $1$
from $G$, resulting in an instance where each type has either $2$ or at least
$3$ neighbors in $C$. For each type of the latter kind, we check if it
contains more members than $\max(3,7-i)+b$; if yes, we reject (or,
equivalently, replace the instance with a trivial constant-size no-instance),
and this is correct by Lemma 3. Moreover, for each type $T$ with precisely $2$
neighbors in $C$ containing more than $3{k}+6+b+1$ many members, we delete
members from $T$ until its size is precisely $3{k}+6+b+1$—the correctness of
this step follows from Lemma 5 and 6.

In the resulting graph, each of the at most $2^{k}$ many types with at least
$3$ neighbors in $C$ has size at most $b+4$, while each of the at most $k^{2}$
types with precisely $2$ neighbors has size at most $3{k}+6+b+1$. The kernel
bound follows. ∎

From Theorem 5.1, the runtime bound given by Theorem 3.1 and the fact that a
vertex cover of size at most $2\cdot\mathbf{vcn}(G)$ can be obtained in linear
time, we obtain:

###### Corollary 2

$b$-bend $\beta$-restricted RAC Drawing is fixed-parameter tractable
parameterized by $b+\mathbf{vcn}(G)$ , and in particular can be solved in time
$2^{2^{\mathcal{O}(\mathbf{vcn}(G)+\log b)}}+\mathcal{O}(|V(G)|)$.

###### Proof

Applying the runtime result of $m^{\mathcal{O}(m^{2})}$ given in Theorem 3.1
to the given kernel yields a final runtime of

$\displaystyle\mathcal{O}(b\cdot
2^{\mathbf{vcn}(G)})^{\mathcal{O}(b^{2}4^{\mathbf{vcn}(G)})}$
$\displaystyle=2^{(\log
b+\mathbf{vcn}(G))\cdot\mathcal{O}(b^{2}4^{\mathbf{vcn}(G)})}$
$\displaystyle\leq 2^{b^{2}\log b\cdot 2^{\mathcal{O}(\mathbf{vcn}(G))}}$
$\displaystyle=2^{2^{(\log\log b)+2\log b}\cdot
2^{\mathcal{O}(\mathbf{vcn}(G))}}$ $\displaystyle=2^{2^{\mathcal{O}(\log
b+\mathbf{vcn}(G))}},$

which concludes the proof. ∎

##  6 An Extension to Neighborhood Diversity

We extend the approach used for the vertex cover number to establish fixed-
parameter tractability with respect to neighborhood diversity. Briefly
recalling the definition of neighborhood diversity, let two vertices
$v,v^{\prime}$ be of the same type if
$N(v)\backslash\\{v^{\prime}\\}=N(v^{\prime})\backslash\\{v\\}$.

######  Definition 3 ([40, 39])

The neighborhood diversity $\mathbf{nd}(G)$ of a graph $G$ is the minimum
number $k$, such that there exists a partition into $k$ sets, where all
vertices in each set have the same type.

By the definition of neighborhood diversity, each set in the witnessing
partition is either an independent set or clique in $G$. Edges can occur
either on all vertices between two sets or on none (see Figure 11). In
general, a graph $G$ with neighborhood diversity $\mathbf{nd}(G)$ has a
bounded vertex cover number $\mathbf{vcn}(G)$. Thus, Theorem 5.1 would already
imply tractability of $b$-bend RAC drawings under a bounded neighborhood
diversity. However, $\mathbf{vcn}(G)$ might be exponentially larger [40]. For
$b$-bend RAC drawable graphs, we can show a better, linear bound on
$\mathbf{vcn}(G)$.

###### Lemma 7

Let $G$ be a $b$-bend RAC drawable graph with a neighborhood diversity
$\mathbf{nd}(G)$. Then $\mathbf{vcn}(G)\leq 5\cdot\mathbf{nd}(G)+b$.

###### Proof

We begin by showing a linear bound on $\mathbf{vcn}(G)$ for $b=0$. Let
$S_{1},\dots,S_{\mathbf{nd}(G)}$ be a partition witnessing the neighborhood
diversity number $\mathbf{nd}(G)$. We build a vertex cover $C$ as follows. The
size of each set $S_{i}$ forming a clique in $G$ is bounded by 5, as a $K_{6}$
is not straight-line RAC drawable [20]. Put all vertices of such an $S_{i}$ in
$C$. Let $S_{i},S_{j}$ be a pair of two sets, which are both forming an
independent set in $G$, and have edges between each other. If there is an edge
between a vertex in $S_{i}$ and a vertex in $S_{j}$, there is an edge between
all vertices of $S_{i}$ and $S_{j}$. Let $|S_{i}|\leq|S_{j}|$. Recalling that
no complete bipartite graph $K_{a,b}$ with $a+b>7$ and $\min(a,b)>2$ admits a
straight-line RAC drawing [19], $S_{i}\leq 3$. Put $S_{i}$ into $C$ to cover
both sets. In total, we put at most $5\cdot\mathbf{nd}(G)$ vertices into $C$.

Figure 11: Overview of a graph partitioned into its neighborhood diversity
sets. Orange sets build cliques, turquoise sets are independent sets in $G$.
Each set may be connected to one ore more other sets.

For arbitrary number of bends $b$, the total number of vertices in clique sets
might increase by at most $b$ without making $G$ not $b$-bend RAC drawable.
Similarly, the number of vertices in the smaller set $S_{i}$ of a connected
set pair $S_{i},S_{j}$, might increase by at most $b$ over all such sets. So
in total, $\mathbf{vcn}(G)\leq 5\cdot\mathbf{nd}(G)+b$. ∎

From Theorem 5.1 and Lemma 7 the following theorem follows directly:

###### Theorem 6.1

$b$-bend $\beta$-restricted RAC Drawing admits a kernel of size
$\mathcal{O}(b^{2}\cdot\mathbf{nd}(G)\cdot 2^{\mathbf{nd}(G)})$.

###### Corollary 3

$b$-bend $\beta$-restricted RAC Drawing is fixed-parameter tractable
parameterized by $\mathbf{nd}(G)+b$, and in particular can be solved in time
$2^{b^{\mathcal{O}(\mathbf{nd}(G))}}+\mathcal{O}(|V(G)|+\mathbf{nd}(G))$.

##  7 Concluding Remarks

We have established the fixed-parameter tractability of $b$-bend
$\beta$-restricted RAC Drawing when parameterized by the feedback edge number
$\mathbf{fen}(G)$, or by the vertex cover number $\mathbf{vcn}(G)$ plus an
upper bound $b$ on the total number of bends. We have also shown that the
latter result implies the fixed-parameter tractability of the problem w.r.t.
the neighborhood diversity $\mathbf{nd}(G)$ plus $b$.

A next step in the computational study of RAC Drawings would be to consider
whether the problem is fixed-parameter tractable w.r.t. $\mathbf{vcn}(G)$
alone. Interestingly, a reduction rule for degree-$2$ vertices without a bound
on $b$ is the main obstacle towards obtaining such a fixed-parameter
algorithm, and dealing with this case seems to be required if one wishes to
generalize the result towards fixed-parameter tractability w.r.t.  _treedepth_
[42] plus $b$. A different question one may ask is whether the fixed-parameter
algorithm w.r.t. $\mathbf{fen}(G)$ can be generalized towards the recently
introduced parameter _slim tree-cut width_ [31], which can be equivalently
seen as a local version of the feedback edge number [12]. A natural long-term
goal within this research direction is then to obtain an understanding of the
complexity of BRAC w.r.t. treewidth [43]. Last but not least, it would be
interesting to see whether our fixed-parameter tractability results can be
strengthened by obtaining polynomial kernels for the same parameterizations.

### Acknowledgments

The authors graciously accept support from the WWTF (Project ICT22-029) and
the FWF (Project Y1329) science funds.

## References

  * [1] Angelini, P., Bekos, M.A., Förster, H., Kaufmann, M.: On RAC drawings of graphs with one bend per edge. Theor. Comput. Sci. 828-829, 42–54 (2020). https://doi.org/10.1016/j.tcs.2020.04.018
  * [2] Angelini, P., Bekos, M.A., Katheder, J., Kaufmann, M., Pfister, M.: RAC drawings of graphs with low degree. In: Szeider, S., Ganian, R., Silva, A. (eds.) 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria. LIPIcs, vol. 241, pp. 11:1–11:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.MFCS.2022.11
  * [3] Angelini, P., Cittadini, L., Didimo, W., Frati, F., Di Battista, G., Kaufmann, M., Symvonis, A.: On the perspectives opened by right angle crossing drawings. J. Graph Algorithms Appl. 15(1), 53–78 (2011). https://doi.org/10.7155/jgaa.00217
  * [4] Argyriou, E.N., Bekos, M.A., Symvonis, A.: The straight-line RAC drawing problem is np-hard. J. Graph Algorithms Appl. 16(2), 569–597 (2012). https://doi.org/10.7155/jgaa.00274
  * [5] Balko, M., Chaplick, S., Ganian, R., Gupta, S., Hoffmann, M., Valtr, P., Wolff, A.: Bounding and computing obstacle numbers of graphs. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany. LIPIcs, vol. 244, pp. 11:1–11:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.ESA.2022.11
  * [6] Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. J. Graph Algorithms Appl. 22(1), 23–49 (2018). https://doi.org/10.7155/jgaa.00457
  * [7] Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic geometry, Algorithms and Computation in Mathematics, vol. 10. Springer (2006). https://doi.org/10.1007/3-540-33099-2, http://link.springer.com/10.1007/3-540-33099-2
  * [8] Bekos, M.A., Didimo, W., Liotta, G., Mehrabi, S., Montecchiani, F.: On RAC drawings of 1-planar graphs. Theor. Comput. Sci. 689, 48–57 (2017). https://doi.org/10.1016/j.tcs.2017.05.039
  * [9] Bhore, S., Ganian, R., Montecchiani, F., Nöllenburg, M.: Parameterized algorithms for book embedding problems. J. Graph Algorithms Appl. 24(4), 603–620 (2020). https://doi.org/10.7155/jgaa.00526
  * [10] Bhore, S., Ganian, R., Montecchiani, F., Nöllenburg, M.: Parameterized algorithms for queue layouts. J. Graph Algorithms Appl. 26(3), 335–352 (2022). https://doi.org/10.7155/jgaa.00597
  * [11] Bieker, N.: Complexity of graph drawing problems in relation to the existential theory of the reals. Ph.D. thesis, Bachelor’s thesis, Karlsruhe Institute of Technology (August 2020) (2020)
  * [12] Brand, C., Ceylan, E., Ganian, R., Hatschka, C., Korchemna, V.: Edge-cut width: An algorithmically driven analogue of treewidth based on edge cuts. In: Bekos, M.A., Kaufmann, M. (eds.) Graph-Theoretic Concepts in Computer Science \- 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers. Lecture Notes in Computer Science, vol. 13453, pp. 98–113. Springer (2022). https://doi.org/10.1007/978-3-031-15914-5_8
  * [13] Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40-42), 3736–3756 (2010). https://doi.org/10.1016/j.tcs.2010.06.026
  * [14] Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000). https://doi.org/10.1007/s002249910009
  * [15] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edn. (2015)
  * [16] Di Giacomo, E., Didimo, W., Eades, P., Liotta, G.: 2-layer right angle crossing drawings. Algorithmica 68(4), 954–997 (2014). https://doi.org/10.1007/s00453-012-9706-7
  * [17] Di Giacomo, E., Didimo, W., Grilli, L., Liotta, G., Romeo, S.A.: Heuristics for the maximum 2-layer RAC subgraph problem. Comput. J. 58(5), 1085–1098 (2015). https://doi.org/10.1093/comjnl/bxu017
  * [18] Didimo, W.: Right angle crossing drawings of graphs. In: Hong, S., Tokuyama, T. (eds.) Beyond Planar Graphs, Communications of NII Shonan Meetings, pp. 149–169. Springer (2020). https://doi.org/10.1007/978-981-15-6533-5_9
  * [19] Didimo, W., Eades, P., Liotta, G.: A characterization of complete bipartite rac graphs. Information Processing Letters 110(16), 687–691 (2010). https://doi.org/10.1016/j.ipl.2010.05.023
  * [20] Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theoretical Computer Science 412(39), 5156–5166 (2011). https://doi.org/10.1016/j.tcs.2011.05.025
  * [21] Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. ACM Comput. Surv. 52(1), 4:1–4:37 (2019). https://doi.org/10.1145/3301281
  * [22] Diestel, R.: Graph Theory, 5th Edition, Graduate Texts in Mathematics, vol. 173. Springer (2017). https://doi.org/10.1007/978-3-662-53622-3
  * [23] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer (2013). https://doi.org/10.1007/978-1-4471-5559-1
  * [24] Eiben, E., Ganian, R., Hamm, T., Klute, F., Nöllenburg, M.: Extending nearly complete 1-planar drawings in polynomial time. In: Esparza, J., Král’, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic. LIPIcs, vol. 170, pp. 31:1–31:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.MFCS.2020.31
  * [25] Eiben, E., Ganian, R., Hamm, T., Klute, F., Nöllenburg, M.: Extending partial 1-planar drawings. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference). LIPIcs, vol. 168, pp. 43:1–43:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.ICALP.2020.43
  * [26] Fleszar, K., Mnich, M., Spoerhase, J.: New algorithms for maximum disjoint paths based on tree-likeness. Math. Program. 171(1-2), 433–461 (2018). https://doi.org/10.1007/s10107-017-1199-3
  * [27] Förster, H., Kaufmann, M.: On compact RAC drawings. In: Grandoni, F., Herman, G., Sanders, P. (eds.) 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference). LIPIcs, vol. 173, pp. 53:1–53:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.ESA.2020.53
  * [28] de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting fáry embeddings of planar graphs. In: Simon, J. (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA. pp. 426–433. ACM (1988). https://doi.org/10.1145/62212.62254
  * [29] Fáry, I.: On straight lines representation of planar graphs. Acta Sci. Math. (Szeged) 11, 229–233 (1948)
  * [30] Ganian, R.: Using neighborhood diversity to solve hard problems. CoRR abs/1201.3091 (2012). https://doi.org/10.48550/arXiv.1201.3091
  * [31] Ganian, R., Korchemna, V.: Slim tree-cut width. In: Dell, H., Nederlof, J. (eds.) 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany. LIPIcs, vol. 249, pp. 15:1–15:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.IPEC.2022.15
  * [32] Ganian, R., Ordyniak, S.: The power of cut-based parameters for computing edge-disjoint paths. Algorithmica 83(2), 726–752 (2021). https://doi.org/10.1007/s00453-020-00772-w
  * [33] Garey, M.R., Johnson, D.S.: Crossing number is np-complete. SIAM Journal on Algebraic Discrete Methods 4(3), 312–316 (1983). https://doi.org/10.1137/0604033
  * [34] Grohe, M.: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. 68(2), 285–302 (2004). https://doi.org/10.1016/j.jcss.2003.07.008
  * [35] Hlinený, P., Sankaran, A.: Exact crossing number parameterized by vertex cover. In: Archambault, D., Tóth, C.D. (eds.) Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11904, pp. 307–319. Springer (2019). https://doi.org/10.1007/978-3-030-35802-0_24
  * [36] Huang, W.: Using eye tracking to investigate graph layout effects. In: Hong, S., Ma, K. (eds.) APVIS 2007, 6th International Asia-Pacific Symposium on Visualization 2007, Sydney, Australia, 5-7 February 2007. pp. 97–100. IEEE Computer Society (2007). https://doi.org/10.1109/APVIS.2007.329282
  * [37] Huang, W., Eades, P., Hong, S.: Larger crossing angles make graphs easier to read. J. Vis. Lang. Comput. 25(4), 452–465 (2014). https://doi.org/10.1016/j.jvlc.2014.03.001
  * [38] Huang, W., Hong, S., Eades, P.: Effects of crossing angles. In: IEEE VGTC Pacific Visualization Symposium 2008, PacificVis 2008, Kyoto, Japan, March 5-7, 2008. pp. 41–46. IEEE Computer Society (2008). https://doi.org/10.1109/PACIFICVIS.2008.4475457
  * [39] Knop, D., Koutecký, M., Masarík, T., Toufar, T.: Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. Log. Methods Comput. Sci. 15(4) (2019). https://doi.org/10.23638/LMCS-15(4:12)2019
  * [40] Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. In: de Berg, M., Meyer, U. (eds.) Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I. Lecture Notes in Computer Science, vol. 6346, pp. 549–560. Springer (2010). https://doi.org/10.1007/978-3-642-15775-2_47
  * [41] Mutzel, P.: An alternative method to crossing minimization on hierarchical graphs. SIAM J. Optim. 11(4), 1065–1080 (2001). https://doi.org/10.1137/S1052623498334013
  * [42] Nešetřil, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28. Springer Berlin Heidelberg (2015). https://doi.org/10.1007/978-3-642-27875-4
  * [43] Robertson, N., Seymour, P.D.: Graph minors. III. planar tree-width. J. Comb. Theory, Ser. B 36(1), 49–64 (1984). https://doi.org/10.1016/0095-8956(84)90013-3
  * [44] Schaefer, M.: Rac-drawability is $\exists\mathbb{R}$-complete. In: Graph Drawing and Network Visualization: 29th International Symposium, GD 2021, Tübingen, Germany, September 14–17, 2021, Revised Selected Papers. p. 72–86. Springer-Verlag, Berlin, Heidelberg (2021). https://doi.org/10.1007/978-3-030-92931-2_5


# Hereditary completeness of Exponential systems
$\\{e^{\lambda_{n}t}\\}_{n=1}^{\infty}$ in their closed span in $L^{2}(a,b)$
and Spectral Synthesis

Elias Zikkos111Department of Mathematics, Khalifa University, Abu Dhabi,
United Arab Emirates,
email address<EMAIL_ADDRESS>and<EMAIL_ADDRESS>and Gajath
Gunatillake222Department of Mathematics and Statistics, American University of
Sharjah, Sharjah, United Arab Emirates,
email address<EMAIL_ADDRESS>
###### Abstract

Suppose that $\\{\lambda_{n}\\}_{n=1}^{\infty}$ is a sequence of distinct
positive real numbers satisfying the conditions
inf$\\{\lambda_{n+1}-\lambda_{n}\\}>0,$ and
$\sum_{n=1}^{\infty}\lambda_{n}^{-1}<\infty.$ We prove that the exponential
system $\\{e^{\lambda_{n}t}\\}_{n=1}^{\infty}$ is hereditarily complete in the
closure of the subspace spanned by $\\{e^{\lambda_{n}t}\\}_{n=1}^{\infty}$ in
the space $L^{2}(a,b)$. We also give an example of a class of compact non-
normal operators defined on this closure which admit spectral synthesis.

Mathematics Subject Classification: 30B60, 30B50, 47A10, 46C05.

Keywords: Müntz-Szász theorem, Exponential Systems, Closed Span, Hereditary
completeness, Spectral Synthesis, Compact Operators.

##  1 Introduction

Let $(a,b)$ be a bounded interval on the real line and let $L^{2}(a,b)$ be the
space of square integrable complex valued functions on $(a,b)$, equipped with
the norm

$||f||_{L^{2}(a,b)}:=\left(\int_{a}^{b}|f(x)|^{2}\,dx\right)^{\frac{1}{2}},$

and endowed with the inner product

$\langle f,g\rangle:=\int_{a}^{b}f(x)\overline{g(x)}\,dx.$

Let $\Lambda$ denote the sequence of distinct positive real numbers
$\\{\lambda_{n}\\}_{n=1}^{\infty}.$ Assume that

$\sum_{n=1}^{\infty}\frac{1}{\lambda_{n}}<\infty,\qquad\text{and}\qquad\lambda_{n+1}-\lambda_{n}\geq
c,$ (1.1)

for some positive constant $c$ and all $n.$ Consider the associated
exponential system $\\{e^{\lambda_{n}t}\\}_{n\in\mathbb{N}}$ of $\Lambda$. We
will denote this system by $E_{\Lambda}$. Let ${\mathcal{H}_{\Lambda}}(a,b)$
denote the closed span of $E_{\Lambda}$ in $L^{2}(a,b).$

Since the series $\sum\lambda_{n}^{-1}$ converges, it follows from the Müntz-
Szász theorem that $E_{\Lambda}$ is $not\,\,complete$ in $L^{2}(a,b)$, that
is, ${\mathcal{H}_{\Lambda}}(a,b)$ is a proper subspace of $L^{2}(a,b)$ (see
[7, Theorem 6.1], [4, Theorem 4.2.6], and [6]). Moreover, $E_{\Lambda}$ is a
$minimal$ system, that is, each function $e^{\lambda_{n}t}$ does not belong to
the closed span of the remaining vectors of $E_{\Lambda}$ in $L^{2}(a,b)$ (see
[7, relation (1.9)]).

It is known that a family $\\{f_{n}\\}$ of functions in a separable Hilbert
space $\cal{H}$ is minimal, if and only if it has a $biorthogonal$ sequence in
$\cal{H}$ (see [5, Lemma 3.3.1]): in other words, there exists a sequence
$\\{g_{n}\\}_{n\in\mathbb{N}}\subset\cal{H}$ so that

$\langle g_{n},f_{m}\rangle=\begin{cases}1,&m=n,\\\ 0,&m\not=n.\end{cases}$

We note that a system in $\cal H$ which is both complete and minimal is called
$exact$. An exact system has a unique biorthogonal family in $\cal H$, however
this family is not necessarily complete in $\cal H$ (see [10]).

Clearly now the system $E_{\Lambda}$ has a unique biorthogonal family
$\\{g_{n}\\}_{n\in\mathbb{N}}$ in the space ${\mathcal{H}_{\Lambda}}(a,b)$,
assuming relation $(\ref{LKcondition})$. We will show that this family is
complete in ${\mathcal{H}_{\Lambda}}(a,b)$, thus the system $E_{\Lambda}$ is a
$Markushevich\,\,basis$ in ${\mathcal{H}_{\Lambda}}(a,b)$. In fact, we will
prove that $E_{\Lambda}$ is a $strong\,\,Markushevich\,\,basis$ in
${\mathcal{H}_{\Lambda}}(a,b)$ (Theorem 1.1). This means that for any disjoint
union of two sets $N_{1}$ and $N_{2}$, such that $\mathbb{N}=N_{1}\cup N_{2}$,
the closed span of the mixed system

$\\{e^{\lambda_{n}t}:\,\,n\in N_{1}\\}\cup\\{g_{n}:\,\,n\in N_{2}\\}$

in $L^{2}(a,b)$ is equal to ${\mathcal{H}_{\Lambda}}(a,b)$. We point out that
the phrase “strong Markushevich basis” is used interchangeably with the phrase
$hereditarily\,\,complete\,\,system$.

######  Theorem 1.1.

Let the sequence $\Lambda=\\{\lambda_{n}\\}_{n=1}^{\infty}$ satisfy the
condition $(\ref{LKcondition})$. Then the exponential system $E_{\Lambda}$ is
$\bf{hereditarily\,\,complete}$ in the space ${\mathcal{H}_{\Lambda}}(a,b)$.

Our work has been inspired by [1] where it was proved that a complete and
minimal exponential system $\\{e^{i\lambda_{n}t}:\,\,n\in\mathbb{N}\\}$ in
$L^{2}(-a,a)$ is hereditarily complete up to one-dimensional effect ([1,
Theorem 1.1]). That is, if $\\{g_{n}:\,\,n\in\mathbb{N}\\}$ is the unique
biorthogonal family to the system $\\{e^{i\lambda_{n}t}:\,\,n\in\mathbb{N}\\}$
in $L^{2}(-a,a)$, then for any disjoint union of two sets $N_{1}$ and $N_{2}$,
such that $\mathbb{N}=N_{1}\cup N_{2}$, the orthogonal complement in
$L^{2}(a,b)$ to the closed span of the mixed system

$\\{e^{i\lambda_{n}t}:\,\,n\in N_{1}\\}\cup\\{g_{n}:\,\,n\in N_{2}\\},$

is at most one dimensional. The latter phenomenon is possible since there
exists an exact exponential system $\\{e^{i\lambda_{n}t}\\}$ in
$L^{2}(-\pi,\pi)$ which is not hereditarily complete ([1, Theorem 1.3]).

######  Remark 1.1.

We point out that our exponential system $E_{\Lambda}$ is not complete in
$L^{2}(a,b)$ but it is hereditarily complete in
${\mathcal{H}_{\Lambda}}(a,b)$.

The notion of hereditary completeness is closely related to the
$Spectral\,\,Synthesis$ problem for linear operators [8, 1, 2, 3]. We say that
a bounded linear operator $T$ in a separable Hilbert space $H$ having a set of
eigenvectors which is complete in $H$, admits $Spectral\,\,Synthesis$ if for
any invariant subspace $A$ of $T$, the set of eigenvectors of $T$ contained in
$A$ is complete in $A$. It follows by the results obtained by J. Wermer in [9]
that an operator which is $\bf both$ compact and normal admits spectral
synthesis. However, if one of the two conditions does not hold, then the
conclusion might not be true. In particular, Wermer gave an example of a
bounded normal operator which does not admit spectral synthesis [9, Theorem
2], while A. S. Markus, amongst others, proved that there exist compact
operators which do not admit spectral synthesis (see [8, Theorem 4.2]).

Markus [8, Theorem 4.1] also showed that a compact operator with a trivial
kernel and non-zero simple eigenvalues with corresponding eigenvectors
$\\{f_{n}\\}$, admits spectral synthesis if and only if the family
$\\{f_{n}\\}$ is hereditarily complete in $\cal H$. Motivated by this result,
and since our system $E_{\Lambda}$ is hereditarily complete in
${\mathcal{H}_{\Lambda}}(a,b)$, we present in Section 4 a class of compact but
not normal operators on ${\mathcal{H}_{\Lambda}}(a,b)$ which admit spectral
synthesis.

##  2 Properties of the space ${\mathcal{H}_{\Lambda}}(a,b)$

Subject to the condition $(\ref{LKcondition})$, Luxemburg and Korevaar proved
in [7, Theorem 8.2] that a function $f$ belongs to the space
${\mathcal{H}_{\Lambda}}(a,b)$ if and only if $f(x)=g(x)$ almost everywhere on
$(a,b)$, where $g$ is an analytic function in the half plane $\Re z<b$,
admitting the Dirichlet series representation

$g(z)=\sum_{n=1}^{\infty}a_{n}e^{\lambda_{n}z}\qquad
a_{n}\in\mathbb{C},\quad\forall\,\,z\in\Re z<b,$

with the series converging uniformly on compact subsets of the half plane $\Re
z<b$.

Let us rewrite the above result using another notation. Consider the space of
square integrable functions on $(a,b)$ that admit a Dirichlet series
representation

$f(z)=\sum_{n=1}^{\infty}c_{n}e^{\lambda_{n}z}$

in the half-plane $\Re z<b$, converging uniformly on compacta. Denote this
space by $L^{2}(a,b,E_{\Lambda})$, that is

$L^{2}(a,b,E_{\Lambda}):=\left\\{f\in
L^{2}(a,b):\,\,f(z)=\sum_{n=1}^{\infty}c_{n}e^{\lambda_{n}z}\quad\forall\,\,z\in\Re
z<b\right\\}.$

The Luxemburg-Korevaar result is now restated as follows.

######  Theorem A.

Let $\\{\lambda_{n}\\}_{n=1}^{\infty}$ be a sequence of numbers satisfying the
condition $(\ref{LKcondition})$. Then

${\mathcal{H}_{\Lambda}}(a,b)=L^{2}(a,b,E_{\Lambda}).$

The above result depends heavily on deriving the distance lower bound
$(\ref{distanceresult})$: let $e_{n}(x):=e^{\lambda_{n}x}$ and let
$E_{\Lambda_{n}}:=E_{\Lambda}\setminus\\{e_{n}\\}$, that is $E_{\Lambda_{n}}$
is the system $E_{\Lambda}$ excluding the function $e^{\lambda_{n}x}$. Denote
by $D_{n}$ the $\bf Distance$ between $e_{n}$ and the closed span of
$E_{\Lambda_{n}}$ in $L^{2}(a,b)$,

$D_{n}:=\inf_{g\in\overline{\text{span}}(E_{\Lambda_{n}})}||e_{n}-g||_{L^{2}(a,b)}.$

It was shown ([7, relation (1.9)]) that for every $\epsilon>0$, there is a
positive constant $m_{\epsilon}$ which does not depend on $n\in\mathbb{N}$,
but only on $\Lambda$ and the segment $(a,b)$, so that

$D_{n}\geq m_{\epsilon}\cdot e^{(b-\epsilon)\lambda_{n}}.$ (2.1)

##  3 Hereditary Completeness: Proof of Theorem 1.1

In this section we prove our hereditary completeness result by first obtaining
the Fourier type series representation $(\ref{representationf})$ for functions
in ${\mathcal{H}_{\Lambda}}(a,b)$.

######  Lemma 3.1.

Let the sequence $\Lambda=\\{\lambda_{n}\\}_{n=1}^{\infty}$ satisfy the
condition $(\ref{LKcondition})$ and consider the space
${\mathcal{H}_{\Lambda}}(a,b)$. Then the following hold.

(I) There exists a family of functions

$r_{\Lambda}=\\{r_{n}:\,\,n\in\mathbb{N}\\}\subset{\mathcal{H}_{\Lambda}}(a,b)$

so that it is the unique biorthogonal sequence to $E_{\Lambda}$ in
${\mathcal{H}_{\Lambda}}(a,b)$. For every $\epsilon>0$ there is a constant
$m_{\epsilon}>0$, independent of $n\in\mathbb{N}$, so that

$||r_{n}||_{L^{2}(a,b)}\leq
m_{\epsilon}e^{(-b+\epsilon)\lambda_{n}},\qquad\forall\,\,n\in\mathbb{N}.$
(3.1)

$(II)$ For each $f$ in ${\mathcal{H}_{\Lambda}}(a,b)$ there exists a function
$g$ analytic in the half-plane $\Re z<b$, so that

$f(x)=g(x)\qquad\text{almost everywhere on}\quad(a,b),$

with $g$ admitting the Fourier-type Dirichlet series representation

$g(z)=\sum_{n=1}^{\infty}\langle f,r_{n}\rangle\cdot e^{\lambda_{n}z},$ (3.2)

converging uniformly on compact subsets of the half-plane $\Re z<b$.

###### Proof.

$(I)$ Recall the distance result $(\ref{distanceresult})$ and the system
$E_{\Lambda_{n}}$. Now, since $L^{2}(a,b)$ is a Hilbert space, it then follows
that there exists a unique element in
$\overline{\text{span}}(E_{\Lambda_{n}})$ in $L^{2}(a,b)$,that we denote by
$\Phi_{n}$, so that

$||e_{n}-\Phi_{n}||_{L^{2}(a,b)}=\inf_{g\in\overline{\text{span}}(E_{\Lambda_{n}})}||e_{n}-g||_{L^{2}(a,b)}=D_{n}.$

The function $e_{n}-\Phi_{n}$ is orthogonal to all the elements of the closed
span of $E_{\Lambda_{n}}$ in $L^{2}(a,b)$, hence to $\Phi_{n}$ itself.
Therefore

$\langle e_{n}-\Phi_{n},e_{n}-\Phi_{n}\rangle=\langle
e_{n}-\Phi_{n},e_{n}\rangle.$

Hence

$(D_{n})^{2}=\langle e_{n}-\Phi_{n},e_{n}\rangle.$

Next, we define

$r_{n}(x):=\frac{e_{n}(x)-\Phi_{n}(x)}{(D_{n})^{2}},\qquad\text{thus}\qquad||r_{n}||_{L^{2}(a,b)}=\frac{1}{D_{n}}.$

It then follows that $\langle r_{n},e_{n}\rangle=1$ and $r_{n}$ is orthogonal
to all the elements of the system $E_{\Lambda_{n}}$. Thus
$\\{r_{n}:\,\,n\in\mathbb{N}\\}$ is biorthogonal to the system $E_{\Lambda}$.
Since $\Phi_{n}\in\overline{\text{span}}(E_{\Lambda_{n}})$ in $L^{2}(a,b)$ it
follows that $r_{n}\in\overline{\text{span}}(E_{\Lambda})$ in $L^{2}(a,b)$.
Moreover, since $||r_{n}||_{L^{2}(a,b)}=1/D_{n}$, then from
$(\ref{distanceresult})$ we obtain $(\ref{rnkbound})$.

$(II)$ From Theorem $A$ we know that if $f$ belongs to
${\mathcal{H}_{\Lambda}}(a,b)$ then $f$ is extended analytically to the half-
plane $\Re z<b$, admitting the series representation
$f(z)=\sum_{m=1}^{\infty}c_{m}e^{\lambda_{m}z}$ for some coefficients
$c_{m}\in\mathbb{C}$, converging uniformly on compacta. We will show below
that

$c_{n}=\langle f,r_{n}\rangle\qquad\text{for\,\, all}\quad n\in\mathbb{N}.$

Fix some $n\in\mathbb{N}$. Then

$\displaystyle\langle f,r_{n}\rangle$ $\displaystyle=$
$\displaystyle\int_{a}^{b}\overline{r_{n}(x)}\cdot\left(\sum_{m=n+1}^{\infty}c_{m}e^{\lambda_{m}x}\right)\,dx+\int_{a}^{b}\overline{r_{n}(x)}\cdot\left(\sum_{m=1}^{n}c_{m}e^{\lambda_{m}x}\right)\,dx$
(3.3) $\displaystyle=$
$\displaystyle\int_{a}^{b}\overline{r_{n}(x)}\cdot\left(\sum_{m=n+1}^{\infty}c_{m}e^{\lambda_{m}x}\right)\,dx+c_{n}$

with the last step valid due to the biorthogonality.

We claim that

$\int_{a}^{b}\overline{r_{n}(x)}\cdot\left(\sum_{m=n+1}^{\infty}c_{m}e^{\lambda_{m}x}\right)\,dx=0.$
(3.4)

Indeed, since $f\in L^{2}(a,b)$, then the Dirichlet series

$Q_{n}(z):=f(z)-\sum_{m=1}^{n}c_{m}e^{\lambda_{m}z}=\sum_{m=n+1}^{\infty}c_{m}e^{\lambda_{m}z}$

also belongs to $L^{2}(a,b)$. It then follows from Theorem $A$ that $Q_{n}$
belongs to the closed span of the exponential system

$E_{\Lambda(n+1)}:=E_{\Lambda}\setminus\\{e^{\lambda_{m}x}:\,m=1,2,\dots,n\\}=\\{e^{\lambda_{m}x}:\,m\geq
n+1\\}$

in $L^{2}(a,b)$. Thus, for every $\epsilon>0$, there is a function
$f_{\epsilon}$ in the span of $E_{\Lambda(n+1)}$ so that
$||Q_{n}-f_{\epsilon}||_{L^{2}(a,b)}<\epsilon$. From biorthogonality we have

$\int_{a}^{b}\overline{r_{n}(x)}\cdot f_{\epsilon}(x)\,dx=0.$

Combining this with the Cauchy-Schwarz inequality we get

$\displaystyle\left|\int_{a}^{b}\overline{r_{n}(x)}\cdot Q_{n}(x)\,dx\right|$
$\displaystyle=$
$\displaystyle\left|\int_{a}^{b}\overline{r_{n}(x)}\cdot(Q_{n}(x)-f_{\epsilon}(x))\,dx\right|$
$\displaystyle\leq$ $\displaystyle\epsilon\cdot||r_{n}||_{L^{2}(a,b)}.$

The arbitrary choice of $\epsilon$ implies that $(\ref{zerozero1})$ is true.

Finally, replacing $(\ref{zerozero1})$ in $(\ref{cnk})$ shows that $\langle
f,r_{n}\rangle=c_{n}$, that is $(\ref{representationf})$ holds.

∎

###  3.1 Proof of Theorem 1.1

Let us write the set $\mathbb{N}$ as an arbitrary disjoint union of two sets
$N_{1}$ and $N_{2}$. In order to obtain the hereditary completeness of
$E_{\Lambda}$ in ${\mathcal{H}_{\Lambda}}(a,b)$, we must show that the closed
span of the mixed system

$E_{1,2}:=\\{e_{n}:\,\,n\in N_{1}\\}\cup\\{r_{n}:\,\,n\in N_{2}\\},$

in $L^{2}(a,b)$ is equal to ${\mathcal{H}_{\Lambda}}(a,b)$.

Denote by $W_{\Lambda_{1,2}}$ the closed span of $E_{1,2}$ in $L^{2}(a,b)$.
Obviously $W_{\Lambda_{1,2}}$ is a subspace of ${\mathcal{H}_{\Lambda}}(a,b)$.
Let $W^{\perp}_{\Lambda_{1,2}}$ be the orthogonal complement of
$W_{\Lambda_{1,2}}$ in ${\mathcal{H}_{\Lambda}}(a,b)$, that is

$W^{\perp}_{\Lambda_{1,2}}=\\{f\in{\mathcal{H}_{\Lambda}}(a,b):\,\,\langle
f,g\rangle=0\quad\text{for\,\, all}\,\,g\in W_{\Lambda_{1,2}}\\}.$

Now, if $f\in W^{\perp}_{\Lambda_{1,2}}\subset{\mathcal{H}_{\Lambda}}(a,b)$
then by $(\ref{representationf})$ we have

$f(t)=\sum_{n=1}^{\infty}\langle f,r_{n}\rangle\cdot
e^{\lambda_{n}t},\quad\text{almost everywhere on}\,\,(a,b)$

and of course $\langle f,r_{n}\rangle=0$ for all $n\in N_{2}$. Thus,

$f(t)=\sum_{n\in N_{1}}\langle f,r_{n}\rangle\cdot
e^{\lambda_{n}t},\quad\text{almost everywhere on}\,\,(a,b).$

Since the above Dirichlet series $f$ is analytic in the half-plane $\Re z<b$
and belongs to $L^{2}(a,b)$, it follows from Theorem $A$ that $f$ belongs to
the closed span of the exponential system

$E_{\Lambda,N_{1}}:=\\{e_{n}:\,\,n\in N_{1}\\}$

in $L^{2}(a,b)$. Hence, for every $\epsilon>0$ there is a function
$g_{\epsilon}$ in $\text{span}(E_{\Lambda,N_{1}})$ so that
$||f-g_{\epsilon}||_{L^{2}(a,b)}<\epsilon$. Write

$\langle f,f\rangle=\langle f,f-g_{\epsilon}\rangle+\langle
f,g_{\epsilon}\rangle.$

Since $f\in W^{\perp}_{\Lambda_{1,2}}$ then $\langle f,e_{n}\rangle=0$ for all
$n\in N_{1}$, thus $\langle f,g_{\epsilon}\rangle=0$. Therefore,

$||f||^{2}_{L^{2}(\gamma,\beta)}=\langle f,f\rangle=\langle
f,f-g_{\epsilon}\rangle\leq||f||_{L^{2}(a,b)}\cdot||f-g_{\epsilon}||_{L^{2}(a,b)}\leq||f||_{L^{2}(a,b)}\cdot\epsilon.$

Hence

$||f||_{L^{2}(a,b)}\leq\epsilon.$

Clearly this means that $f(x)=0$ almost everywhere on $(a,b)$, hence
$W^{\perp}_{\Lambda_{1,2}}=\\{\mathbf{0}\\}$. Thus
$W_{\Lambda_{1,2}}={\mathcal{H}_{\Lambda}}(a,b)$, meaning that the exponential
system $E_{\Lambda}$ is hereditarily complete in the space
${\mathcal{H}_{\Lambda}}(a,b)$. The proof of Theorem 1.1 is now complete.

##  4 Compact operators on ${\mathcal{H}_{\Lambda}}(a,b)$ admitting Spectral
Synthesis

Our goal in this section is to present a class of compact but not normal
operators on ${\mathcal{H}_{\Lambda}}(a,b)$ that admit Spectral Synthesis. The
operators constructed will have the properties presented below, a result
obtained by Markus.

######  Theorem B.

[8, Theorem 4.1]

Let $T:\cal{H}$$\to\cal{H}$ be a compact operator such that

(i) its kernel is trivial and

(ii) its non-zero eigenvalues are $\bf simple$.

Let $\\{f_{n}\\}_{n\in\mathbb{N}}$ be the corresponding sequence of
eigenvectors. Then $T$ admits $\bf{Spectral\,\,Synthesis}$ if and only if
$\\{f_{n}\\}_{n\in\mathbb{N}}$ is $\bf Hereditarily\,\,complete$ in $\cal{H}$.

###  4.1 A class of operators on ${\mathcal{H}_{\Lambda}}(a,b)$

Let $f$ be a function in the space ${\mathcal{H}_{\Lambda}}(a,b)$. Then from
Lemma 3.1 we have

$f(z)=\sum_{n=1}^{\infty}\langle f,r_{n}\rangle\cdot e_{n}(z),$

with the series converging uniformly on compact subsets of the half-plane $\Re
z<b$. From relation $(\ref{rnkbound})$, for every $\epsilon>0$ there exists
some $m_{\epsilon}>0$, independent of $n\in\mathbb{N}$, so that

$|\langle f,r_{n}\rangle|\leq||f||_{L^{2}(a,b)}\cdot
m_{\epsilon}e^{(-b+\epsilon)\lambda_{n}}.$

Let $\delta>0$ and choose a sequence $\\{u_{n}\\}_{n=1}^{\infty}$ of distinct
non-zero complex numbers such that

$|u_{n}|\leq e^{-\delta\lambda_{n}}.$ (4.1)

Clearly $u_{n}\to 0$ as $n\to\infty$.

######  Example 4.1.

For $\delta>0$, we may take $u_{n}=e^{-\delta\lambda_{n}}$.

It follows from above that for every $0<\epsilon<\delta$, there exists some
$m_{\epsilon}>0$, independent of $n\in\mathbb{N}$ and
$f\in{\mathcal{H}_{\Lambda}}(a,b)$, so that

$|\langle f,r_{n}\rangle\cdot u_{n}|\leq||f||_{L^{2}(a,b)}\cdot
m_{\epsilon}e^{(-b-\delta+\epsilon)\lambda_{n}}.$ (4.2)

Now, define

$T(f(z)):=\sum_{n=1}^{\infty}\langle f,r_{n}\rangle\cdot u_{n}\cdot
e^{\lambda_{n}z}.$ (4.3)

One deduces from $(\ref{upperbound})$ that $T(f(z))$ is a function analytic in
the half-plane $\Re z<b+\delta$, converging uniformly on compact subsets of
this half-plane, thus on the interval $[a,b]$ as well. The uniform convergence
on $[a,b]$ implies that

$(i)$ $T(f(z))$ belongs to the space ${\mathcal{H}_{\Lambda}}(a,b)$.

$(ii)$ The series $T(f)$ converges in the $L^{2}(a,b)$ norm.

######  Remark 4.1.

It also follows from $(\ref{upperbound})-(\ref{operator})$ that there exists
some $N>0$ so that

$||T(f)||_{L^{2}(a,b)}\leq N||f||_{L^{2}(a,b)}\quad\text{for\,\, all}\quad
f\in{\mathcal{H}_{\Lambda}}(a,b).$

Therefore, $T:{\mathcal{H}_{\Lambda}}(a,b)\to{\mathcal{H}_{\Lambda}}(a,b)$
defines a Bounded Linear Operator. We denote by $T^{*}$ its Adjoint operator.

We will show that

######  Theorem 4.1.

The operator $T:{\mathcal{H}_{\Lambda}}(a,b)\to{\mathcal{H}_{\Lambda}}(a,b)$
defined in $(\ref{operator})$ is compact, not normal, and admits spectral
synthesis.

###### Proof.

Our result follows from Lemmas $\ref{compactoperator}-\ref{notnormal}$,
Theorem $B$, and the fact that the system $E_{\Lambda}$ is hereditarily
complete in ${\mathcal{H}_{\Lambda}}(a,b)$. ∎

We remark that if we choose $u_{n}=e^{-\delta\lambda_{n}}$ as in Example 4.1,
then $T(f(z))$ is equal to the translation $f(z-\delta)$, which is well
defined on ${\mathcal{H}_{\Lambda}}(a,b)$ since any function in this space
extends analytically to the half-plane $\Re z<b$. Thus we have

######  Corollary 4.1.

For any $\delta>0$, the shift operator $T_{\delta}(f):=f(z-\delta)$ defined on
${\mathcal{H}_{\Lambda}}(a,b)$ is compact, not normal, and admits spectral
synthesis.

###  4.2 Auxiliary results: Lemmas 4.1, 4.2, 4.3, and 4.4

In the following four lemmas, we prove that the operator $T$ is compact, we
obtain various properties of $T$ as those stated in Theorem $B$, and we show
that $T$ is not normal. Finally, a Fourier type series representation is
derived for the adjoint $T^{*}$.

If $L$ is a bounded operator on ${\mathcal{H}_{\Lambda}}(a,b)$, we use $\|L\|$
to denote the operator norm of $L$ which is the supremum of the set
$\\{\|L(f)\|_{L^{2}(a,b)}:f\in{\mathcal{H}_{\Lambda}}(a,b),\|f\|_{L^{2}(a,b)}=1\\}$.

######  Lemma 4.1.

The operator $T$ is compact.

###### Proof.

Let $e_{n}(x)=e^{\lambda_{n}x}.$ Define $T_{m}$ on
${\mathcal{H}_{\Lambda}}(a,b)$ by

$T_{m}(g)(x)=\sum_{n=1}^{m}\langle g,r_{n}\rangle u_{n}e_{n}(x).$

Let $f$ be a unit vector in ${\mathcal{H}_{\Lambda}}(a,b)$. It is easy to see
that

$\|(T-T_{m})(f)\|_{L^{2}(a,b)}\leq\sum_{n=m+1}^{\infty}\|\langle
f,r_{n}\rangle u_{n}e_{n}\|_{L^{2}(a,b)}.$

We have that $\|\langle f,r_{n}\rangle u_{n}e_{n}\|_{L^{2}(a,b)}\leq
m_{\epsilon}e^{(-b-\delta+\epsilon)\lambda_{n}}\|e_{n}\|_{L^{2}(a,b)}.$ It is
easy to see that $\|e_{n}\|_{L^{2}(a,b)}<e^{\lambda_{n}b}.$ Thus, $\|\langle
f,r_{n}\rangle u_{n}e_{n}\|_{L^{2}(a,b)}\leq
m_{\epsilon}e^{(-\delta+\epsilon)\lambda_{n}}.$ Therefore,

$\|(T-T_{m})(f)\|_{L^{2}(a,b)}\leq
m_{\epsilon}\sum_{n=m+1}^{\infty}e^{(-\delta+\epsilon)\lambda_{n}}.$

Since $\delta>\epsilon,$ the series above converges. Hence, $\|T-T_{m}\|$
tends to zero as $m$ tends to infinity. Thus, the finite rank operators
$\\{T_{m}\\}$ converge to $T$ in the uniform operator topology. Therefore, $T$
is compact. ∎

######  Lemma 4.2.

The following are true about the operator $T$ and its adjoint.

  1. 1.

$\\{u_{k}\\}_{k=1}^{\infty}$ are eigenvalues of $T$ and
$\\{e_{k}\\}_{k=1}^{\infty}$ are the corresponding eigenvectors.

  2. 2.

$\\{\overline{u_{k}}\\}$ are eigenvalues of $T^{*}$ and
$\\{r_{k}\\}_{k=1}^{\infty}$ are the corresponding eigenvectors.

  3. 3.

The kernel of $T$ is trivial.

  4. 4.

The spectrum of $T$ is $\displaystyle{\\{0\\}\cup\\{u_{k}\\}_{k=1}^{\infty}}$.

  5. 5.

Each eigenvalue of $T$ is simple.

###### Proof.

1\. Due to the biorthogonal relation between $E_{\Lambda}$ and $r_{\Lambda}$,
we see in $(\ref{operator})$ that

$T(e_{k})=u_{k}e_{k}.$

2\. For fixed $k\in\mathbb{N}$ and any $n\in\mathbb{N}$ we have

$\displaystyle\langle T^{*}r_{k}-\overline{u_{k}}r_{k},e_{n}\rangle$
$\displaystyle=$ $\displaystyle-\overline{u_{k}}\langle
r_{k},e_{n}\rangle+\langle r_{k},Te_{n}\rangle$ (4.4) $\displaystyle=$
$\displaystyle-\overline{u_{k}}\langle r_{k},e_{n}\rangle+\langle
r_{k},u_{n}e_{n}\rangle$ $\displaystyle=$
$\displaystyle-\overline{u_{k}}\langle
r_{k},e_{n}\rangle+\overline{u_{n}}\langle r_{k},e_{n}\rangle.$

If $n=k$ then $(\ref{zero})$ equals zero, and the same holds for all $n\not=k$
due to the biorthogonal relation between $r_{\Lambda}$ and $E_{\Lambda}$ .
Thus $\langle T^{*}r_{k}-\overline{u_{k}}r_{k},e_{n}\rangle=0$ for all
$n\in\mathbb{N}$, hence

$T^{*}r_{k}-\overline{u_{k}}\cdot r_{k}=\mathbf{0}.$

3\. We now show that the kernel of $T$ is the zero set. For any
$n\in\mathbb{N}$ we have

$\langle Tf,r_{n}\rangle=\langle f,T^{*}r_{n}\rangle=\langle
f,\overline{u_{n}}r_{n}\rangle.$

If $Tf=0$ then one has $\langle f,r_{n}\rangle=0$ for all $n\in\mathbb{N}$.
Since the family $\\{r_{n}\\}_{n=1}^{\infty}$ is complete in the space
${\mathcal{H}_{\Lambda}}(a,b)$, then $f=\mathbf{0}$. Hence the kernel of $T$
is the zero function.

4\. Next we prove that $\\{u_{k}\\}$ are the only non-zero eigenvalues.
Suppose that $Tf=\lambda f$ for some $\lambda\notin\\{u_{n}\\}_{n=1}^{\infty}$
and $f\not=\mathbf{0}$. Then,

$\displaystyle\lambda\langle f,r_{n}\rangle$ $\displaystyle=\langle
Tf,r_{n}\rangle,$ $\displaystyle=\langle f,T^{*}r_{n}\rangle,$
$\displaystyle=\langle f,\overline{u_{n}}r_{n}\rangle,$
$\displaystyle=u_{n}\langle f,r_{n}\rangle.$ (4.5)

Thus,

$(\lambda-u_{n})\cdot\langle f,r_{n}\rangle=0$

for all $n.$ But $\lambda\notin\\{u_{n}\\}_{n=1}^{\infty}$ therefore $\langle
f,r_{n}\rangle=0$ for all $n\in\mathbb{N}$. Since the family
$\\{r_{n}\\}_{n=1}^{\infty}$ is complete in the space
${\mathcal{H}_{\Lambda}}(a,b)$, then $f=\mathbf{0}$. This contradiction shows
that $\\{u_{k}\\}$ are the only non-zero eigenvalues. Since $T$ is compact it
follows that the spectrum of $T$ is

$\displaystyle{\\{0\\}\cup\\{u_{k}\\}_{k=1}^{\infty}}.$

5\. Next we prove that each eigenvalue of $T$ is simple. Suppose that
$Tf=u_{k}f$ for some $u_{k}\in\\{u_{n}\\}_{n=1}^{\infty}$ and some
$f\in{\mathcal{H}_{\Lambda}}(a,b)$. Then, using the same computation in (4.5)
above, we get

$(u_{k}-u_{n})\langle f,r_{n}\rangle=0\qquad$

for all $n.$ But if $n\not=k,$ then $u_{n}\not=u_{k}$, thus, $\langle
f,r_{n}\rangle=0$ for all $n\not=k$. Since

$f(t)=\sum_{n=1}^{\infty}\langle f,r_{n}\rangle\cdot e_{n}(t),$

then we get $f(t)=\langle f,r_{k}\rangle e_{k}$. But this means that $u_{k}$
is simple.

∎

######  Lemma 4.3.

The operator $T$ is not normal.

###### Proof.

Suppose that $T$ is a normal operator, thus

$TT^{*}(e_{k})=T^{*}T(e_{k})\qquad\text{for\,\,all}\quad k\in\mathbb{N}.$

But any two eigenvectors that correspond to different eigenvalues of a normal
operator are orthogonal. Clearly this is not the case here for the set of
eigenvectors $e_{n}=e^{\lambda_{n}t}$ of $T$. ∎

And finally, biorthogonality of $\\{e_{n}\\}$ and $\\{r_{n}\\}$ allows us to
compute $T^{*}$ explicitly.

######  Lemma 4.4.

The adjoint operator $T^{*}$ of $T$ admits the representation

$T^{*}f(z)=\sum_{n=1}^{\infty}\langle f,e_{n}\rangle\cdot\overline{u_{n}}\cdot
r_{n}(z),$ (4.6)

with the series converging uniformly on compact susbets of the half-plane $\Re
z<b$. The series also converges in the $L^{2}(a,b)$ norm.

###### Proof.

Given $f\in{\mathcal{H}_{\Lambda}}(a,b)$,

(I) We first prove that the series

$g_{f}(z):=\sum_{n=1}^{\infty}\langle f,e_{n}\rangle\cdot\overline{u_{n}}\cdot
r_{n}(z)$ (4.7)

converges uniformly on compact susbets of the half-plane $\Re z<b$.

$(II)$ We then show that $g_{f}$ belongs to the space
${\mathcal{H}_{\Lambda}}(a,b)$ and $g_{f}$ converges in the $L^{2}(a,b)$ norm.

$(III)$ And finally we prove that

$\langle Th,f\rangle=\langle h,g_{f}\rangle\qquad\text{for\,\, all}\quad
h\in{\mathcal{H}_{\Lambda}}(a,b).$

$(I)$ Consider first an arbitrary compact subset $K$ of the half plane $\Re
z<b$, such that $\Re z\leq A$ for all $z\in K$ for some $A<b$. From the
Fourier-type Dirichlet series representation $(\ref{representationf})$, we
have

$r_{n}(z)=\sum_{m=1}^{\infty}\langle r_{n},r_{m}\rangle e^{\lambda_{m}z}$

with the series converging uniformly on $K$. Also, from $(\ref{rnkbound})$,
for every $\epsilon>0$ there exists a positive constant $M_{\epsilon}$ so that

$|\langle r_{n},r_{m}\rangle|\leq M_{\epsilon}\cdot
e^{(-b+\epsilon)\lambda_{n}}\cdot e^{(-b+\epsilon)\lambda_{m}}.$

Take $0<\epsilon<b-A$ thus $-b+\epsilon+A<0$. Then

$|r_{n}(z)|\leq M_{\epsilon}\cdot
e^{(-b+\epsilon)\lambda_{n}}\cdot\sum_{m=1}^{\infty}e^{(-b+\epsilon)\lambda_{m}}\cdot
e^{A\lambda_{m}}\quad\text{for\,\, all}\quad z\in K.$

Since $-b+\epsilon+A<0$, this means that there is some positive constant
$P_{K}$ which depends on the set $K$, and not on $n\in\mathbb{N}$, so that

$|r_{n}(z)|\leq P_{K}\cdot M_{\epsilon}\cdot
e^{(-b+\epsilon)\lambda_{n}}\quad\text{for\,\, all}\quad z\in K.$

Now, from $(\ref{un})$, the Cauchy-Schwarz inequality and since
$e_{n}(t)=e^{\lambda_{n}t}$, one gets

$|\langle f,e_{n}\rangle\cdot\overline{u_{n}}|\leq||f||_{L^{2}(a,b)}\cdot
e^{\lambda_{n}b}\cdot e^{-\delta\lambda_{n}}.$

Combining the above bounds shows that

$|\langle f,e_{n}\rangle\cdot\overline{u_{n}}\cdot r_{n}(z)|\leq P_{K}\cdot
M_{\epsilon}\cdot||f||_{L^{2}(a,b)}\cdot
e^{(-\delta+\epsilon)\lambda_{n}}\quad\text{for\,\, all}\quad z\in K.$

Since $\epsilon<\delta$, the above shows that the series $g_{f}$
$(\ref{seriesgf})$ converges uniformly on $K$.

$(II)$ Next, for every $n\in\mathbb{N}$ let

$V_{n}(z):=\langle f,e_{n}\rangle\cdot\overline{u_{n}}\cdot r_{n}(z),$

thus

$g_{f}(z)=\sum_{n=1}^{\infty}V_{n}(z).$

It then follows from relations $(\ref{rnkbound})$ and $(\ref{un})$, that for
every $\epsilon\in(0,\delta)$, there is a positive constant $M_{\epsilon}$, so
that

$\displaystyle||V_{n}(t)||_{L^{2}(a,b)}$ $\displaystyle=$
$\displaystyle|\langle f,e_{n}\rangle|\cdot|u_{n}|\cdot||r_{n}||_{L^{2}(a,b)}$
$\displaystyle\leq$ $\displaystyle M_{\epsilon}\cdot||f||_{L^{2}(a,b)}\cdot
e^{\lambda_{n}b}\cdot e^{-\delta\lambda_{n}}\cdot
e^{(-b+\epsilon)\lambda_{n}}.$

Thus

$||V_{n}(t)||_{L^{2}(a,b)}\leq M_{\epsilon}\cdot||f||_{L^{2}(a,b)}\cdot
e^{(-\delta+\epsilon)\lambda_{n}}.$

Since $\epsilon<\delta$ then

$\sum_{n=1}^{\infty}||V_{n}(t)||_{L^{2}(a,b)}<\infty.$ (4.8)

Consider now the function

$H(t):=\sum_{n=1}^{\infty}|V_{n}(t)|=\sum_{n=1}^{\infty}|\langle
f,e_{n}\rangle\cdot\overline{u_{n}}|\cdot|r_{n}(t)|\qquad\forall\,\,t\in(a,b).$
(4.9)

From $(\ref{Vnt})$ and the Minkowski inequality, we see that $H$ belongs to
the space $L^{2}(a,b)$. Clearly $|g_{f}(t)|\leq H(t)$ for all $t\in(a,b)$,
thus $g_{f}$ belongs to $L^{2}(a,b)$ as well.

We also claim that $g_{f}$ converges in the $L^{2}(a,b)$ norm. Indeed, we have

$\left|\left(g_{f}(t)-\sum_{n=1}^{M}V_{n}(t)\right)\right|^{2}=\left|\left(\sum_{n=M+1}^{\infty}V_{n}(t)\right)\right|^{2}\leq\left(\sum_{n=M+1}^{\infty}|V_{n}(t)|\right)^{2}\leq
H^{2}(t).$

Moreover, $|g_{f}(t)-\sum_{n=1}^{M}V_{n}(t)|^{2}\to 0$ as $M\to\infty$ for all
$t\in(a,b)$. Then by the Lebesgue Convergence Theorem we have

$||g_{f}-\sum_{n=1}^{M}V_{n}||_{L^{2}(a,b)}\to 0\qquad\text{as}\qquad
M\to\infty.$ (4.10)

Finally, it is clear that each $V_{n}$ belongs to the space
${\mathcal{H}_{\Lambda}}(a,b)$. Together with $(\ref{tozeroU})$ yields that
$g_{f}$ also belongs to the space ${\mathcal{H}_{\Lambda}}(a,b)$.

$(III)$ Next, let $h\in{\mathcal{H}_{\Lambda}}(a,b)$. It follows from
$(\ref{rnkbound})$ and $(\ref{un})$ that

$|\overline{f(t)}\cdot\langle h,r_{n}\rangle\cdot u_{n}\cdot e_{n}(t)|\leq
m_{\epsilon}e^{(-\delta+\epsilon)\lambda_{n}}\cdot||h||_{L^{2}(a,b)}\cdot|f(t)|\qquad\text{for\,\,
all}\quad t\in(a,b).$

This justifies below interchanging the integral sign with the summation sign

$\displaystyle\langle Th,f\rangle$ $\displaystyle=$
$\displaystyle\int_{a}^{b}\overline{f(t)}\cdot\left(\sum_{n=1}^{\infty}\langle
h,r_{n}\rangle\cdot u_{n}\cdot e_{n}(t)\right)\,dt$ (4.11) $\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\langle h,r_{n}\rangle\cdot
u_{n}\cdot\int_{a}^{b}\overline{f(t)}\cdot e_{n}(t)\,dt$ $\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\langle h,r_{n}\rangle\cdot u_{n}\cdot\langle
e_{n},f\rangle.$

Consider then the function $H$ as in $(\ref{H})$ with $H\in L^{2}(a,b)$ as
discussed before. For any $M\in\mathbb{N}$, one has

$|\sum_{n=1}^{M}\langle f,e_{n}\rangle\cdot\overline{u_{n}}\cdot
r_{n}(t)|\leq|H(t)|\qquad\text{for\,\, all}\quad t\in(a,b).$

From this upper bound and the Lebesgue Convergence Theorem, we can interchange
below the integral sign with the summation sign to get

$\displaystyle\langle h,g_{f}\rangle$ $\displaystyle=$
$\displaystyle\int_{a}^{b}h(t)\cdot\overline{\left(\sum_{n=1}^{\infty}\langle
f,e_{n}\rangle\cdot\overline{u_{n}}\cdot r_{n}(t)\right)}\,dt$ (4.12)
$\displaystyle=$ $\displaystyle\sum_{n=1}^{\infty}\langle e_{n},f\rangle\cdot
u_{n}\cdot\int_{a}^{b}h(t)\overline{r_{n}(t)}\,dt$ $\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\langle e_{n},f\rangle\cdot u_{n}\cdot\langle
h,r_{n}\rangle.$

But $(\ref{check2})$ is identical to $(\ref{check})$, thus we conclude that
$\langle Th,f\rangle=\langle h,g_{f}\rangle$. Clearly this holds for all
$h\in{\mathcal{H}_{\Lambda}}(a,b)$ and therefore

$\langle h,T^{*}f\rangle=\langle h,g_{f}\rangle\qquad\text{for\,\, all}\quad
h\in{\mathcal{H}_{\Lambda}}(a,b).$

By the uniqueness of the adjoint operator $T^{*}$, the formula
$(\ref{adjoint})$ for $T^{*}$ is valid. ∎

## References

  * [1] A. Baranov, Y. Belov, A. Borichev, Hereditary completeness for systems of exponentials and reproducing kernels, Adv. Math. $\bf 235$ (2013), 525–554.
  * [2] A. Baranov, Y. Belov, A. Borichev, Spectral Synthesis in de Branges Spaces, Geom. Funct. Anal. $\bf 25$ (2015), 417–452.
  * [3] A. Baranov, Y. Belov, A. Kulikov, Spectral synthesis for exponentials and logarithmic length, Isr. J. Math. $\bf 250$ (2022), 403–427.
  * [4] P. Borwein, T. Erdélyi, Polynomials and polynomial inequalities, Springer-Verlag, New-York, 1995. x+480 pp. ISBN: 0-387-94509-1.
  * [5] O. Christensen, An introduction to Frames and Riesz Bases, Applied and Numerical Harmonic Analysis. Birkhäuser Boston, Inc., Boston, MA, xxii+440 pp. ISBN: 0-8176-4295-1 (2003).
  * [6] V. I. Gurariy, W. Lusky, Geometry of Müntz spaces and related questions, Lecture Notes in Mathematics, 1870. Springer-Verlag, Berlin, 2005. xiv+172 pp. ISBN 978-3-540-28800-8; 3-540-28800-7.
  * [7] W. A. J. Luxemburg, J. Korevaar, Entire functions and Müntz-Szász type approximation, Trans. Amer. Math. Soc. $\bf 157$ (1971), 23–37.
  * [8] A. S. Markus, The problem of spectral synthesis for operators with point spectrum, Math. USSR Izv. $\bf 4$ no. 3 (1970), 670–696.
  * [9] J. Wermer, On invariant subspaces of normal operators, Proc. Amer. Math. $\bf 3$ no. 2 (1952), 270–277.
  * [10] R. M. Young, On complete biorthogonal systems, Proc. Amer. Math. Soc. $\bf 83$ no. 3 (1981), 537–540.
  * [11] R. M. Young, An introduction to Nonharmonic Fourier Series, Revised first edition. Academic Press, Inc., San Diego, CA, (2001) xiv+234 pp. ISBN: 0-12-772955-0.