# Recognizing Geometric Intersection Graphs Stabbed by a Line

Dibyayan Chakraborty111Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard
Lyon 1, LIP UMR5668, France Kshitij Gajjar222Indian Institute of Technology
Jodhpur, India Irena Rusu333Nantes Université, École Centrale Nantes, CNRS,
LS2N, UMR 6004, F-44000 Nantes, France

###### Abstract

In this paper, we determine the computational complexity of recognizing two
graph classes, grounded └-graphs and stabbable grid intersection graphs. An
└-shape is made by joining the bottom end-point of a vertical ($|$) segment to
the left end-point of a horizontal ($-$) segment. The top end-point of the
vertical segment is known as the anchor of the └-shape. Grounded └-graphs are
the intersection graphs of └-shapes such that all the └-shapes’ anchors lie on
the same horizontal line. We show that recognizing grounded └-graphs is
$\NP$-complete. This answers an open question asked by Jelínek & Töpfer
(Electron. J. Comb., 2019).

Grid intersection graphs are the intersection graphs of axis-parallel line
segments in which two vertical (similarly, two horizontal) segments cannot
intersect. We say that a (not necessarily axis-parallel) straight line $\ell$
stabs a segment $s$, if $s$ intersects $\ell$. A graph $G$ is a stabbable grid
intersection graph (StabGIG) if there is a grid intersection representation of
$G$ in which the same line stabs all its segments. We show that recognizing
StabGIG graphs is $\NP$-complete, even when the input graphs are restricted to
be bipartite apex graphs of large (but constant) girth. This answers an open
question asked by Chaplick et al. (Order, 2018).

##  1 Introduction

Recognizing a graph class means deciding whether a given graph is a member of
the graph class. In this paper, we deal with the computational complexity of
recognizing intersection graphs of certain types of geometric objects in the
plane. These recognition problems stemmed from various fields of active
research, like VLSI design [11, 12, 26], map labelling [1], wireless networks
[21], computational biology [29], and have now become an indelible part of
computational geometry.

Perhaps the most extensively studied class of geometric intersection graphs is
the class of _interval graphs_ (intersection graphs of intervals on the real
line), introduced by Benzer [5] while studying the fine structure of genes. In
1962, Lekkerkerker & Boland [22] proved that the class of interval graphs is
precisely the class of graphs without _holes_ 444A hole is an induced cycle
with $4$ or more vertices. and _asteroidal triples_ 555Three vertices of a
graph form an asteroidal triple if the removal of any one of the vertices
(along with all its neighbouring vertices) from the graph does not disconnect
the other two.. The above elegant result of Lekkerkerker & Boland [22]
motivated researchers to study further generalizations of interval graphs and
their characterizations. One such generalization was considered by Gyárfás and
Lehel [16] who considered the class of _└ -intersection graphs_. An _└ -shape_
[16] is a couple made of a vertical and horizontal segment, whose bottom and
left end-points coincide. _└ -intersection graphs_ are the intersection graphs
of └-shapes. Observe that interval graphs can be expressed as intersection
graphs of └-shapes as follows: given an interval representation of a graph,
replace each interval with an └-shape whose horizontal segment is the same as
the interval on the horizontal line $y=0$. The popularity of └-graphs among
graph theorists increased when Gonçalves [15] proved that all planar graphs
(graphs that can be drawn in the plane in such a way that edges can intersect
only at their end-points) are └-graphs. In contrast, recognizing └-graphs is
$\NP$-complete even if the inputs are restricted to apex graphs [9] (see
Definition 1 below).

An interesting subclass of └-graphs called _infinite- └-graphs_ was considered
by McGuinness [23]. The top end-point of the vertical segment of an └-shape is
called the anchor of the └-shape. _Infinite- └-graphs_, also known as
_grounded └-graphs_ are the intersection graphs of └-shapes whose anchors
belong to the same horizontal line, called the _ground line_. See Figure 1 for
an example. Interval graphs are (also) grounded └-graphs. (Indeed, given a set
of intervals, replace each interval with an └-shape whose horizontal segment
is the same as the interval on the horizontal line $y=0$ and whose anchor lies
on the horizontal line $y=1$). Other well-studied subclasses of grounded
└-graphs are (see [2]) outerplanar graphs, permutation graphs, circle graphs
etc. Researchers have studied different aspects (e.g. chromatic number [23,
13], dominating set [8], independent set [7], forbidden patterns [18]) of
grounded └-graphs. However, the complexity of recognizing grounded └-graphs
remained open. In this paper, we prove that recognizing grounded └-graphs is
$\NP$-complete answering a question asked by Jelínek and Töpfer [18].

######  Theorem 1.

Recognizing grounded └-graphs is $\NP$-complete.

|  |  $\ell$ |  |
---|---|---|---|---

Figure 1: A graph (left) with its grounded └-shape representations (middle)
and its stabbable grid intersection representation (right).

A “two-dimensional” analogue of interval graphs is the class of _rectangle
intersection graphs_ (i.e., intersection graphs of axis-parallel rectangles in
the plane). This graph class was introduced by Asplund & Grünbaum [3] in 1960,
who studied the chromatic number of such graphs. After almost three decades,
Kratochvíl [19] proved that recognizing rectangle intersection graphs is
$\NP$-complete, even if the input graphs are restricted to bipartite graphs.
Interestingly, bipartite rectangle intersection graphs are exactly the class
of grid intersection graphs (GIG), i.e., intersection graphs of axis-parallel
line segments in the plane where no two segments with the same orientation
intersect [17]. This implies that the recognition of GIG is $\NP$-complete,
and motivates the study of its subclasses. Chaplick et al.  [10] introduced
the class of _stabbable grid intersection graphs_. A segment $s$ in the plane
is _stabbed_ by a line $\ell$ if $s$ and $\ell$ intersect. A graph $G$ is a
_stabbable grid intersection graph_ (StabGIG) if it has a grid intersection
representation such that there exists a straight line that stabs all the
segments of the representation. See Figure 1 for an example. All planar
bipartite graphs are StabGIGs [14] and Chaplick et al. [10] left the problem
of recognizing stabbable grid intersection graphs as open. In this paper, we
answer their question.

######  Definition 1.

[28, 27]. A graph is an apex graph if it contains a vertex whose removal makes
it planar.

######  Theorem 2.

For every fixed positive integer $g\geq 10$, recognizing StabGIG is
$\NP$-complete, even when the input graphs are restricted to bipartite apex
graphs of girth exactly $g$.

Organisation: In Sections 2 and 3, we prove Theorem 1 and Theorem 2,
respectively. In Section 4, we conclude.

Notations: For a positive integer $n\geq 1$, $[n]$ denotes the set
$\\{1,2,\ldots,n\\}$. All graphs considered in this paper are simple and
undirected. For a graph $G$, the sets $V(G)$ and $E(G)$ denote the vertex set
and edge set of $G$, respectively.

Convention: Both for grounded └-graphs and StabGIGs, we assume without loss of
generality that any two segments in the representation intersect in at most
one point. Otherwise, slight changes in the position and length of the
segments allow to transform a representation that does not have this property
into a convenient one.

##  2 Proof of Theorem 1

In our presentation, the geometrical representation of the grounded └-graphs
uses  └ -shapes above the horizontal ground line rather than └-shapes below
it. For a grounded └-graph, this representation is its grounded  └
-representation. Note that the convention above implies that all the anchors
are distinct.

The  └ -shape representing a vertex $x$ is denoted by
$\rotatebox[origin={c}]{180.0}{\lx@text@tweaked{yoffset=-0.5ex}{\lx@mvs@RoundedLSteel}}(x)$,
and the anchor of
$\rotatebox[origin={c}]{180.0}{\lx@text@tweaked{yoffset=-0.5ex}{\lx@mvs@RoundedLSteel}}(x)$,
now located at the bottom of the vertical segment, is denoted by $x$ too. The
left to right order of the anchors along the ground line is denoted by
$\prec$. Note that for two intersecting  └ -shapes  └ $(x)$ and  └ $(y)$, we
have $x\prec y$ if and only if the vertical segment of  └ $(x)$ intersects the
horizontal segment of  └ $(y)$. A  └ -shape that has intersections only on its
vertical (respectively horizontal) segment is called a  └ v-shape
(respectively a  └ h-shape).

$a_{1}$$b_{2}$$a_{2}$$a_{3}$$b_{1}$$b_{1}$$b_{1}$$b_{2}$$b_{2}$$a_{3}$$b_{2}$$a_{1}$$b_{1}$$a_{1}$$a_{2}$$a_{3}$$a_{1}$$a_{2}$$a_{2}$$a_{3}$

Figure 2: Transforming a stick representation into a grounded  └
-representation. Here, the stick graph is the induced path
$a_{1}b_{1}a_{2}b_{2}a_{3}$.

Then the problem we are interested in may be restated as follows:

Grounded └-Graphs Recognition (Grounded └-Rec) Input: A graph $H$. Question:
Is there a grounded  └ -representation for $H$?
---

Then Theorem 1 is equivalent to the statement that Grounded └-Rec is
$\NP$-complete.

In order to show it, we use another class of geometric intersection graphs,
namely stick graphs. They have been defined in [10] as the intersection graphs
of a set $A$ of vertical segments in the plane and a set $B$ of horizontal
segments in the plane, such that the bottom end-point of the segments in $A$
and the left end-point of the segments in $B$ belong to a ground straight line
with slope -1. Again, all the endpoints may be considered as distinct. Stick
graphs are bipartite graphs, and the aforementioned geometrical representation
is called their stick representation.

We prove Theorem 1 using a reduction from the problem below, which is
$\NP$-complete [25]:

Stick Graphs Recognition (StickRec) Input: A bipartite graph $G=(A\cup B,E)$.
Question: Is there a Stick representation of $G$ with sets $A$ and $B$?
---

Grounded └-graphs and stick graphs are related by the following relationship,
which is essential to our construction.

######  Proposition 3.

All stick graphs are grounded └-graphs. Moreover, each stick graph has a
grounded  └ -representation in which the vertices in $A$ are represented by  └
h-shapes, and those in $B$ by  └ v-shapes.

###### Proof.

Let $G$ be a stick graph. Figure 2 illustrates the steps of the proof.
Consider a stick representation of $G$, and replace first each vertical
(respectively horizontal) segment with a  └ -shape having the same anchor as
the initial segment, whose horizontal (respectively vertical) segment is not
used for intersections. Then extend the horizontal segments of the  └ -shapes
towards left so that to place all the anchors on the same vertical line, that
becomes the new ground line. Finally, perform a 90 degrees counterclockwise
rotation of the whole representation to obtain a grounded  └ -representation
of $G$. In this representation, the vertices in $A$ are represented by  └
h-shapes, and those in $B$ by  └ v-shapes. ∎

######  Remark 1.

Not all the bipartite grounded └-graphs are stick graphs. The bipartite graph
in Figure 3 is not a stick graph [10], but is a grounded └-graph as shown by
the  └ -representation we provide.

$a_{1}$

$a_{2}$

$a_{3}$

$a_{4}$

$b_{1}$

$b_{2}$

$b_{3}$

$b_{4}$

$x_{1}$

$y_{1}$

$y_{2}$

$y_{3}$

$x_{2}$

$x_{3}$

$b_{1}$$a_{1}$$a_{2}$$b_{2}$$b_{3}$$a_{3}$$a_{4}$$x_{1}$$y_{1}$$x_{2}$$y_{2}$$b_{4}$$y_{3}$$x_{3}$

Figure 3: An example of a bipartite grounded └-graph, which is not a stick
graph. The bipartition is indicated by the two colours of the vertices, white
and black. In the grounded  └ -representation presented here, the thick  └
-shapes correspond to the black vertices.

###  2.1 The reduction

Our reduction from StickRec to Grounded └-Rec strongly relies on Proposition
3. It transforms a given bipartite graph $G=(A\cup B,E)$ into a (non-
bipartite) graph $H$ that is roughly a copy of $G$ where each vertex $x$ from
$B$ is placed inside a gadget graph called $\Lambda(x)$. The role of the
gadgets is to force the grounded  └ -representation of $G$ produced inside any
grounded  └ -representation of $H$ (if any) to be stick-like, that is, to
represent the vertices in $A$ by  └ h-shapes and the vertices in $B$ by  └
v-shapes. In this way, a grounded  └ -representation exists for $H$ if and
only if a stick representation exists for $G$.

More formally, let $\Lambda(x)$ be the graph in Figure 4 (left). Consider an
instance $G=(A\cup B,E)$ of StickRec, and build an instance $H$ of Grounded
└-Rec as follows:

  1. 1.

for each $a\in A$, define a vertex $a$ of $H$.

  2. 2.

for each $b\in B$, consider a copy of $\Lambda(b)$ such that for each pair
$b\neq b^{\prime}$, the graphs $\Lambda(b)$ and $\Lambda(b^{\prime})$ are
disjoint.

  3. 3.

for each edge $ab\in E$ with $a\in A$ and $b\in B$, add an edge from $a$ to
every vertex in $\Lambda(b)$.

See Figure 4 (right) for an example. We show in the next section that this
reduction proves the $\NP$-completeness of Grounded └-Rec.

$\Lambda(b_{1})$$\Lambda(b_{2})$$a_{1}$$a_{2}$$a_{3}$

Figure 4: The graph $\Lambda(x)$ (left) and the construction of the graph $H$
when $G$ is the path $a_{1}b_{1}a_{2}b_{2}a_{3}$ (right).

###  2.2 The proofs

The gadget $\Lambda(x)$ has been chosen so as to have very few and convenient
grounded  └ -representations.

######  Proposition 4.

The graph $\Lambda(x)$ is a grounded └-graph. It admits exactly two grounded
└ -representations, given in Figures 5(a) and 5(b).

###### Proof.

The proof consists of a case study. The vertices 1, 2, 3, 4 induce a complete
subgraph, whose grounded  └ -representation is unique up to the labelling of
the anchors. It consists of four  └ -shapes whose anchors are ordered from
left to right along the ground line, such that the horizontal segment of each
└ -shape intersects the vertical segments of all the  └ -shapes located to its
left. The four anchors may be labelled from left to right with any permutation
$\pi$ of 1, 2, 3, 4. Taking into account the symmetry between the (ordered)
triplets $(1,2,5)$ and $(4,3,6)$ we can reduce the number of permutations to
the 12 of them whose leftmost element is 1 or 2. Once a permutation $\pi$ is
fixed, several (at most three) subcases appear depending on the position of
the anchor of  └ $(5)$. As the grounded  └ -representation is progressively
completed by adding  └ -shapes corresponding to new vertices, all of the
representations but one fail to place all the anchors. Below, the numbers
correspond to anchors, and it is assumed that the reader draws himself the
exact form of each  └ -shape so that only the correct intersections occur. We
also assume that the  └ -shapes for the anchors 1, 2, 3, 4 are already drawn
according to the order given by $\pi$.

  * •

$\pi=1234$. a) When $5\prec 1$, there are three possible positions for 6, but
none of them allows to place $x$. b) When $2\prec 5\prec 3$, there are four
possible positions for $6$, but when $3\prec 6\prec 4$ there is no possible
place for $10$, and when $6\prec 1$, there is no place for $x$. When $5\prec
6\prec 3$ or $4\prec 6$, the anchor $x$ is placed either before $1$ (when
$5\prec 6\prec 3$) or between 3 and 4 (for both positions of $6$). When
$x\prec 1$, there is no way to place $9$. Then we must have $3\prec x\prec 4$,
in which case we have $8\prec 1$ (for both positions of $6$) or $6\prec 8$
(only when $1\prec 6$), and thus there is no possible place for the anchor 11
such that  └ $(11)$ intersects  └ $(x)$ and  └ $(8)$ but none of  └ $(1)$,  └
$(2)$,  └ $(3)$,  └ $(4)$. c) When $4\prec 5$, there are four possible
positions for 6, but there is no way to place $x$ when $4\prec 6\prec 5$. When
$2\prec 6\prec 3$ or $3\prec 6\prec 4$, we necessarily have $5\prec x$,
$9\prec 1$ and $3\prec 8\prec 6$ (possible only when $3\prec 6\prec 4$). Then
$11$ cannot be placed. When $6\prec 1$, we necessarily have $x\prec 6$ and
$1\prec 9\prec 2$, which leaves no place for $11$.

  * •

$\pi=1243$. a) When $5\prec 1$, among the four possible positions for $6$ only
$5\prec 6\prec 1$ allows finding a place for $x$ (between $5$ and $6$). But
then $9$ cannot be placed. b) When $2\prec 5\prec 4$, there are four possible
positions for $6$. When $6\prec 1$, one cannot find a position for $x$. When
$5\prec 6\prec 4$, we have $x\prec 1$, and there is no available position for
$9$. When $4\prec 6\prec 3$ or $3\prec 6$, we can find a position for $x$
(between $2$ and $5$). Then the unique possible position for $9$, satisfying
$9\prec 1$, does not allow us to find a position for $11$. c) When $3\prec 5$,
the position of $6$ between $2$ and $4$ does not allow to place $x$. When
$6\prec 1$, we must have $x\prec 6$, and then $9$ cannot be placed. Finally,
when $4\prec 6\prec 3$ or $3\prec 6\prec 5$, we necessarily have $4\prec
x\prec 3$ and $9\prec 1$, so there is no appropriate place for $11$.

  * •

$\pi=1324$. In this case, we deduce $5\prec 1$ and $2\prec 6\prec 4$, and $10$
cannot be placed.

Figure 5: (a)(b) The two grounded  └ -representations of $\Lambda(x)$. The
second one is obtained from the first one by the following renumbering: switch
the numbers $1$ and $4$, then switch the numbers $2$ and $3$, and finally
switch the numbers $5$ and $6$. (c) The drawing replaces each of them, when
only  └ $(x)$ and the level of the lowest horizontal segment need to be known.

  * •

$\pi=1342$. a) When $5\prec 1$, we have two possible positions for $6$, but
none of them allows us to place $x$. b) When $1\prec 5\prec 3$, there are
three possible positions for $6$, namely $4\prec 6\prec 2$ and $2\prec 6$, and
both of them allow to place $x$ (between $3$ and $4$). There is a unique
position for $9$, namely $9\prec 1$, and then $11$ cannot be placed. c) When
$4\prec 5\prec 2$, there are two possible positions for $6$, none of which
allows to place $x$.

  * •

$\pi=1423$. Then $5\prec 1$ and $2\prec 6\prec 3$, and $10$ cannot be placed.

  * •

$\pi=1432$. a) When $5\prec 1$, we have either $3\prec 6\prec 2$ or $2\prec
6$. In the former case, there is no possibility to place $10$, so we
necessarily have $2\prec 6$, in which case $2\prec 10\prec 6$. We also have
unique positions for $x$ and $9$, with $4\prec x\prec 3$ and $4\prec 9\prec
x$. There are three possible positions for $8$, namely: $5\prec 8\prec 1$,
$3\prec 8\prec 2$ and $2\prec 8\prec 10$. Only $2\prec 8\prec 10$ allows to
place $11$, whose  └ -shape must intersect  └ $(x)$,  └ $(8)$ and  └ $(9)$,
and then $x\prec 11\prec 3$. Then $12$ is placed between $10$ and $6$. This is
the unique grounded  └ -representation of $\Lambda(x)$ when symmetry is left
apart and it is illustrated in Figure 5(a). b) When $1\prec 5\prec 4$, we have
$6\prec 1$, $3\prec 6\prec 2$ or $2\prec 6$. The latter case does not allow to
find a position for $10$. The case $3\prec 6\prec 2$ does not allow finding a
position for $x$. Then we must have $6\prec 1$ and thus $6\prec x\prec 1$,
since this is the only possible choice for $x$. Then $9\prec 6$ is the only
place for $9$ that allows a position for $11$, which must satisfy $9\prec
11\prec 6$. But then $8$ cannot be placed such as  └ $(8)$ intersects  └
$(x)$,  └ $(9)$,  └ $(11)$,  └ $(2)$ and  └ $(3)$. c) When $3\prec 5\prec 2$,
two cases occur for $6$. When $6\prec 1$, we have $4\prec x\prec 3$, $4\prec
9\prec x$ and either $6\prec 8\prec 1$ or $3\prec 8\prec 5$. None of the cases
allows placing $11$. When $3\prec 6\prec 5$, we have again $4\prec x\prec 3$.
We also have $8\prec 1$ or $6\prec 8\prec 5$, and either $9\prec 1$ (and even
$9\prec 8\prec 1$ in the former case) or $4\prec 9\prec x$. In all cases,
there is no place for $11$.

  * •

$\pi=2134$. a) When $5\prec 2$, there are four possible positions for $6$, but
none of them allows to place $x$. b) When $1\prec 5\prec 3$, the unique
position of $6$ that allows placing $x$ is $5\prec 6\prec 3$. In this case, we
have $x\prec 2$ and $9$ must satisfy $5\prec 9\prec 6$. But then there is no
appropriate place for $11$. c) When $4\prec 5$, among the four possible
positions for $6$ only $6\prec 2$ allows to find a place for $x$, which
satisfies then $x\prec 6$. Then $3\prec 9\prec 4$ and $11$ cannot be placed.

  * •

$\pi=2143$. a) When $5\prec 2$, three cases occur. With $5\prec 6\prec 2$, we
deduce that $2\prec x\prec 1$ and $10$ satisfies $6\prec 10\prec 2$. Then
either $2\prec 8\prec x$ or $4\prec 8\prec 3$, and in both cases $12$ cannot
be placed. With $4\prec 6\prec 3$, there is no possible place for $10$. With
$1\prec 6\prec 4$ or $3\prec 6$, we have $4\prec x\prec 3$. Moreover, with
$2\prec 8\prec 1$ one cannot find a position for $11$, so that we must have
$x\prec 8\prec 3$, thus forbidding the position of $6$ to the right of $3$
(since  └ $(8)$ and  └ $(6)$ do not intersect). But then there is no possible
place for $10$. b) When $1\prec 5\prec 4$, $x$ must be to the left of $1$,
otherwise  └ $(x)$ cannot intersect  └ $(2)$,  └ $(3)$ and  └ $(5)$. Then
$6\prec 2$ is the only appropriate position for $6$, and it implies $2\prec
x\prec 1$, and $6\prec 10\prec 2$. Concerning $8$, the position $8\prec 6$
does not allow to place $11$, so only $4\prec 8\prec 3$ is possible. Then
there is no possible place for $12$. c) When $3\prec 5$, among the $4$
possible positions for $6$ the one with $1\prec 6\prec 4$ does not allow to
find a position for $x$. When $6\prec 2$, we must have $x\prec 6$ and either
$4\prec 9\prec 3$ or $3\prec 9\prec 5$. Then there is no appropriate place for
$11$. When $4\prec 6\prec 3$ or $3\prec 6\prec 5$, we have $4\prec x\prec 3$
(and even $4\prec x\prec 6\prec 3$ when $6$ is between $4$ and $3$) and either
$8\prec 2$ or $2\prec 8\prec 1$. None of them allows placing $11$.

  * •

$\pi=2314$. Then $5\prec 2$, $1\prec 6\prec 4$ and 10 cannot be placed.

  * •

$\pi=2341$. a) When $5\prec 2$, we cannot have $4\prec 6\prec 1$ since there
is no available position for $10$, so we necessarily have $1\prec 6$ and
$1\prec 10\prec 6$. The only possible places for $x$ and $8$ satisfy $1\prec
x\prec 10$ and $3\prec 8\prec 4$. But then $11$ cannot be placed. b) When
$2\prec 5\prec 3$, three positions exist for $6$, with $6\prec 2$, $4\prec
6\prec 1$ and $1\prec 6$. The latter one does not allow placing 10. For the
two former cases, we have $3\prec x\prec 4$. But then when $6\prec 2$, there
is no appropriate place for $10$. We deduce that $4\prec 6\prec 1$, and thus
there is a unique place for $10$, such that $5\prec 10\prec 3$. Concerning
$8$, the two positions satisfying $8\prec 2$ and respectively $1\prec 8$ are
correct, but none of them allows to find a position for $12$. c) When $4\prec
5\prec 1$, only two positions are appropriate for $6$: $6\prec 2$ and $4\prec
6\prec 5$. The latter one does not allow to find a place for $x$, so we
necessarily have $6\prec 2$, and thus $10\prec 6$. Then there is a unique
position for $8$, with $3\prec 8\prec 4$, and it is impossible to find a place
for $12$.

  * •

$\pi=2413$. We deduce that $5\prec 2$ and $1\prec 6\prec 3$, and therefore
$10$ cannot be placed.

  * •

$\pi=2431$. a) When $5\prec 2$, we deduce that $1\prec 6$ or $3\prec 6\prec
1$. In both cases, $x$ cannot be placed. b) When $2\prec 5\prec 4$, none of
the three positions that are possible for $6$ allows to find a place for $x$.
c) When $3\prec 5\prec 1$, we have either $6\prec 2$ or $3\prec 6\prec 5$.
When $3\prec 6\prec 5$, there is no place for $x$. When $6\prec 2$, we must
have $x\prec 6$ and $8\prec x$, so that it is not possible to find a place for
$10$.

Thus there is precisely one grounded  └ -representation when $\pi$ is one of
the 12 permutations whose leftmost value is either $1$ or $2$. This grounded
└ -representation is obtained with $\pi=1432$ in case a), i.e., with $5\prec
1$. Figure 5(a) illustrates it. Because of the symmetry between the triplets
$(1,2,5)$ and $(4,3,6)$, exactly one other grounded  └ -representation is
possible. It occurs in the case $\pi=4123$ and is obtained by simultaneously
switching the labels of all the pairs of symmetric vertices, namely $1$ and
$4$, $2$ and $3$, as well as $5$ and $6$. It is illustrated in Figure 5(b). ∎

Convention. In the remainder of the proof, each of the grounded  └
-representations in Figures 5(a) and 5(b) is drawn as a grey box around  └
$(x)$, together with two short lateral segments indicating the level of the
lowest horizontal segment in the representation. See Figure 5(c).

Let $\Lambda(x)+u$ be the graph obtained by adding to $\Lambda(x)$ a new
vertex $u$ adjacent to all the vertices in $\Lambda(x)$. Then $u$ is called
universal with respect to $\Lambda(x)$.

######  Proposition 5.

The graph $\Lambda(x)+u$ is a grounded └-graph. In its two grounded  └
-representations, $u$ is the rightmost anchor and thus  └ $(u)$ is a  └
h-shape.

###### Proof.

A grounded  └ -representation of $\Lambda(x)+u$ is obtained by placing the
anchor of $u$ to the extreme right of the grounded  └ -representation of
$\Lambda(x)$, and letting the horizontal segment of  └ $(u)$ intersect the
vertical segments of all the other  └ -shapes at a very low height (lower than
the horizontal segment of  └ $(12)$). Then  └ $(u)$ is a  └ h-shape. The
conclusion of Proposition 5 is reached by noticing that, with the  └
-representation in Figure 5(a), any possible alternate position for $u$
necessarily belongs to the interval defined by $2$ and $8$ (so that  └ ($6$),
└ ($12$),  └ ($10$) and  └ ($8$) can be intersected by  └ $(u)$), but then  └
$(u)$ cannot intersect  └ $(2)$. ∎

######  Proposition 6.

The graph $G$ is a yes-instance of StickRec if and only if the graph $H$ is a
yes-instance of Grounded └-Rec.

###### Proof.

For the forward direction, Proposition 3 implies that the stick graph $G$ has
a grounded  └ -representation. We transform this representation of $G$ into a
grounded  └ -representation of $H$ as follows. For each $b\in B$, build a
grounded  └ -representation of $\Lambda(b)$ (whose existence is ensured by
Proposition 4) as a block, in the immediate neighborhood of  └ $(b)$. See
Figure 6. The lowest horizontal segment of a  └ -shape in this grounded  └
-representation of $\Lambda(b)$, indicated in the figure by the two grey
lateral segments of the grey box, must be placed above all the horizontal
segments of  └ -shapes  └ $(a)$ with $a\in A$ and $ab\in E$. This is always
possible, by increasing the lengths of the vertical segments as needed.
Furthermore, for each $a\in A$ such that $ab\in E$, extend the horizontal
segment of  └ $(a)$ such that it intersects all the  └ -shapes representing
vertices in $\Lambda(b)$. The resulting grounded  └ -representation is a
grounded  └ -representation of $H$.

$a_{2}$$a_{3}$$b_{1}$$a_{1}$$b_{2}$$b_{2}$$a_{1}$$b_{1}$$a_{2}$$a_{3}$

Figure 6: The grounded  └ -representation of $G$ (left) and the grounded  └
-representation of $H$ (right), when $G$ is the induced path
$a_{1}b_{1}a_{2}b_{2}a_{3}$ (right).

We now consider the backward direction and assume that we have a grounded  └
-representation for $H$. Let $a\in A,b\in B$ such that $ab\in E$. By the
construction of $H$, $a$ is universal for $\Lambda(b)$. By Proposition 5, we
deduce that  └ $(a)$ is a  └ h-shape when only the subgraph $\Lambda(b)+a$ of
$H$ is considered. It follows that the intersection between  └ $(b)$ and  └
$(a)$ holds on the vertical segment of  └ $(b)$, and on the horizontal segment
of  └ $(a)$, for each pair $a\in A,b\in B$ such that $ab\in E$. Then the
grounded  └ -representation of $G$ may be transformed into a stick-
representation of $G$ by successively transforming the horizontal ground line
into a vertical ground line, and then into a ground line with slope -1, and by
finally removing the unused segments (just following the steps in Figure 2 in
the reverse order). ∎

Now, we are ready to prove that Grounded └-Rec is $\NP$-complete.

###### Proof.

(of Theorem 1). According to [20], and since the number of directions of the
segments in the representation is fixed, Grounded └-Rec is in NP. Proposition
6 shows that our reduction is correct. Moreover, it takes linear time to build
$H$ knowing $G$, so that the reduction is polynomial. ∎

##  3 Proof of Theorem 2

In this section, we focus on the following problem:

Stabbable Grid Intersection Graphs Recognition (StabGIGRec) Input: A bipartite
graph $G$. Question: Is there a grid intersection representation of $G$ in
which all segments are stabbed by the same straight line?
---

Theorem 2 claims that StabGIGRec is $\NP$-complete even when the input graphs
are restricted to bipartite apex graphs of girth $g$, for any given positive
integer $g\geq 10$. Our proof technique is similar to that of Chakraborty &
Gajjar [9]. As in their proof, we use a reduction from the problem below. A
_Hamiltonian path_ in a graph is a path that visits each vertex of the graph
exactly once.

Planar Hamiltonian Path Completion Problem (PHPC) Input: A planar graph $G$.
Question: Is $G$ a subgraph of a planar graph with a Hamiltonian path?
---

###  3.1 The reduction

Convention. Throughout our proof, we will assume that $G$ is a connected graph
with at least five vertices, as every graph on four vertices is planar and the
planarity of a non-connected graph is reduced to that of its components.

Let $k$ be a fixed positive odd number. Given a planar graph $P$ on $p\geq 5$
vertices, we construct a bipartite apex graph
$P_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ in $\poly(p)$ time as
follows.

Let $P_{k\operatorname{-{\mathsf{div}}}}$ be the full $k$-subdivision of $P$,
i.e., $P_{k\operatorname{-{\mathsf{div}}}}$ is the graph obtained by replacing
each edge of $P$ with a path of length $k+1$. Formally, we replace each
$e=xy\in E(P)$ with the path $(x,u^{1}_{e},u^{2}_{e},\ldots,u^{k}_{e},y)$ (see
Figure 7).

$\displaystyle V(P_{k\operatorname{-{\mathsf{div}}}})$
$\displaystyle=V(P)\cup\\{u^{1}_{e},u^{2}_{e},\ldots,u^{k}_{e}\mid e\in
E(P)\\};$ $\displaystyle E(P_{k\operatorname{-{\mathsf{div}}}})$
$\displaystyle=\\{xu^{1}_{e},u^{1}_{e}u^{2}_{e},\ldots,u^{k}_{e}y\mid e=xy\in
E(P)\\}.$

$x$

$y$

$x$

$u_{e}^{1}$

$u_{e}^{2}$

$u_{e}^{3}$

$u_{e}^{4}$

$u_{e}^{5}$

$u_{e}^{6}$

$u_{e}^{7}$

$y$

Figure 7: An edge $e=xy$ (left) and a 7-subdivision of $e$ (right).

We call the vertices of $V(P)\subseteq V(P_{k\operatorname{-{\mathsf{div}}}})$
as the _original vertices_ of $P_{k\operatorname{-{\mathsf{div}}}}$ and the
remaining vertices as the _subdivision vertices_ of
$P_{k\operatorname{-{\mathsf{div}}}}$. Finally, we construct
$P_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ by adding a new vertex
$a$ (called the ‘apex’) to $P_{k\operatorname{-{\mathsf{div}}}}$ and making it
adjacent to all the original vertices of
$P_{k\operatorname{-{\mathsf{div}}}}$. Formally,
$P_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is defined as follows.

$\displaystyle V(P_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}})$
$\displaystyle=V(P_{k\operatorname{-{\mathsf{div}}}})\cup\\{a\\};$
$\displaystyle E(P_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}})$
$\displaystyle=E(P_{k\operatorname{-{\mathsf{div}}}})\cup\\{av\mid v\in
V(P)\\}.$

The reduction from PHPC to StabGIGRec associates to the planar graph $G$, the
input of PHPC, the graph
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ built as above, with
$P=G$ and $k$ an arbitrary but fixed odd integer such that $k\geq 7$. See
Figure 8 for an example of the reduction. We have:

######  Observation 7 ([9]).

If $G$ is a connected planar graph and $g,k$ are positive integers such that
$k$ is odd and $k=g-3\geq 3$, then
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is a bipartite apex
graph of girth exactly $g$.

The graph $G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ thus has the
properties required in Theorem 2 (which requires $g\geq 10$, thus $k=g-3\geq
7$). Moreover, the proposition below holds, and will significantly shorten the
proof of our theorem. A graph is a 1-string graph if it is the intersection
graph of simple curves in the plane, also called strings, such that any two
strings intersect at most once, and whenever they intersect they cross each
other.

######  Proposition 8 ([9]).

Let $k\geq 3$ be an odd integer. If
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is a 1-string graph,
then $G$ is a yes-instance of PHPC.

###  3.2 The proofs

We need to prove that $G$ is a yes-instance of PHPC if and only if
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is a yes-instance of
StabGIGRec. This section presents the forward direction.

$v_{1}$ $v_{2}$ $v_{3}$ $v_{4}$ $v_{5}$ $v_{6}$ $v_{7}$ $v_{8}$ $v_{9}$ $v_{10}$ |  $v_{1}$ $v_{2}$ $v_{3}$ $v_{4}$ $v_{5}$ $v_{6}$ $v_{7}$ $v_{8}$ $v_{9}$ $v_{10}$ |  $v_{1}$ $v_{2}$ $v_{3}$ $v_{4}$ $v_{5}$ $v_{6}$ $v_{7}$ $v_{8}$ $v_{9}$ $v_{10}$ $a$
---|---|---
(a) | (b) | (c)

Figure 8:  (a) An example graph $G$ which is a yes-instance of PHPC. (b) Each
edge of the graph is replaced with a path with $k+1$ edges, where $k\geq 7$.
(A dashed curve indicates a path of length $k+1$.) (c) The apex graph
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, constructed by adding
one extra vertex (the apex vertex $a$) in
$G_{k\operatorname{-{\mathsf{div}}}}$.

######  Proposition 9.

Let $k\geq 7$ be an odd integer. If $G$ is a yes-instance of PHPC, then
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is a StabGIG.

The proof of this result is presented in Sections 3.2.1 to 3.2.3. Section
3.2.4 contains the proof of Theorem 2.

We use the notation $(x,y)$, where $x$ and $y$ are real values, for the
Cartesian coordinates of a point, and the notation
$[(x_{1},y_{1}),(x_{2},y_{2})]$ for the segment whose endpoints are
$(x_{1},y_{1})$ and $(x_{2},y_{2})$.

####  3.2.1 Overview of the construction

In view of proving Proposition 9, let $V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$.
We start with a plane drawing of $G$, i.e., a drawing of $G$ in the plane, in
which the vertices are points and the edges are strings (that is, simple
curves). Then we modify the drawing in a step-by-step manner to end with a
StabGIG representation of
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$. Let us now provide an
overview of these steps.

  1. (a)

Consider a drawing of $G$ in the plane in which the vertex $v_{i}$ (for every
$i\in[n]$) has the Cartesian coordinate $(0,i-1)$, each edge of $G$ crosses
the y-axis (the line $x=0)$ at most once, and no edge of $G$ crosses the
y-axis between $y=0$ and $y=n-1$. (Auer & Gleißner [4] show that such a
drawing exists for every graph that is a yes-instance of PHPC.) See Figure
8(a) for an illustration, where $v_{1}$ is located at $(0,0)$ and $v_{10}$ is
located at $(0,9)$.

  2. (b)

In this drawing, though no edge of $G$ crosses the y-axis between the points
$(0,0)$ and $(0,n-1))$, there might be edges of $G$ that cross the y-axis
below $y=0$ or above $y=n-1$. We place new vertices on the intersection points
of those edges with the y-axis, to create a new graph $H$. Let $n_{H}$ be the
number of vertices in $H$. See Figure 9 for an illustration, where there are
three such vertices, indicated by square nodes.

  3. (c)

The graph $H$ has some nice properties. Firstly, $n\leq n_{H}\leq 4n$.
Secondly, $H$ is a subdivision of $G$. As subdivision does not affect
planarity, $H$ is also planar. Thirdly, the drawing of $H$ ensures that no
edge of $H$ crosses the y-axis. We fix the line $y=x$ as our stab line $\ell$
(recall that $\ell$ does need not to be axis-parallel), and use the current
plane drawing of $H$ to devise a StabGIG representation of the graph
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$. (The graph
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is obtained as
described in the previous section, by considering $P=H$ and $k=3$. See Figure
9.) Note that the graph
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is obtained from
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ by further subdividing
some of its edges.

  4. (d)

In the StabGIG representation of
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, the apex segment of
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is represented by a
long vertical segment coinciding with the y-axis. The $n_{H}$ original
vertices of $H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ are
represented by $n_{H}$ horizontal segments, each one crossing the y-axis at
the point defined by its corresponding vertex in the plane representation of
$H$. Each edge $e=xy$ of $H$ (which is a string in the plane drawing of $H$)
becomes a path with three intermediate vertices
$u_{e}^{1},u_{e}^{2},u_{e}^{3}$ in
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$. These three vertices
are represented as three segments that form a $\sqcup$-shape or a
$\sqcap$-shape, whose two vertical segments appropriately intersect the
horizontal segments representing respectively $x$ and $y$. See Figure 10 for
an illustration (formal details are given below).

  5. (e)

So far, our construction is similar to the construction in [9]. But now, we
have to slightly deviate from it. For each edge $e$ of $H$, we need to very
precisely and carefully describe the positions of the three segments
corresponding to its three subdivision vertices (which will form a
$\sqcup$-shape or a $\sqcap$-shape) $u^{1}_{e},u^{2}_{e},u^{3}_{e}$ in
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, in such a way that
all the three segments intersect the stab line $\ell$. This is the most novel
and non-trivial part of our proof. See Figure 10 for an illustration.

  6. (f)

Lastly, we need to convert
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ to
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$. Note that
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}\setminus\\{a\\}$ is a
subdivision of $G$ in which each edge of $G$ is subdivided either 3 or 7
times. It is easy to add more segments to the StabGIG representation to ensure
that all the edges of $G$ are subdivided exactly $k$ times, for any odd number
$k\geq 7$. An overview of this construction is illustrated by Figure 11.
Finally, with the apex segment $[(0,0),(0,n-1)]$, we have a StabGIG
representation of $G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$.

$v_{1}$

$v_{2}$

$v_{3}$

$v_{4}$

$v_{5}$

$v_{6}$

$v_{7}$

$v_{8}$

$v_{9}$

$v_{10}$

$a$

Figure 9: The graph $H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$,
constructed from the the graph $G$ shown in Figure 8(a). Note that $H$ is
obtained from $G$ by introducing three new vertices (indicated by square
nodes) by subdividing the three edges that cross the y-axis, namely
$v_{2}v_{4}$, $v_{5}v_{7}$ and $v_{5}v_{9}$. The graph
$G_{7\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is then obtained from
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ by introducing 4
additional subdivision vertices for all edges $v_{i}v_{j}$ of $G$ (except
$v_{2}v_{4}$, $v_{5}v_{7}$ and $v_{5}v_{9}$).

####  3.2.2 Construction of
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ and its StabGIG
representation

Now we commence with the formal proof of Proposition 9. Let us start with item
(a). Since $G$ is a yes-instance of PHPC, according to Auer & Gleißner [4],
the edge set $E(G)$ can be partitioned into three sets $E_{\mathsf{left}}(G)$,
$E_{\mathsf{right}}(G)$, and $E_{\mathsf{cross}}(G)$, such that $G$ admits a
plane drawing satisfying the following properties.

  * •

For every $i\in[n]$, the vertex $v_{i}$ has the Cartesian coordinate
$(0,i-1)$.

  * •

Every edge $e\in E_{\mathsf{left}}(G)$ lies in the half-plane $x\leq 0$.

  * •

Every edge $e\in E_{\mathsf{right}}(G)$ lies in the half-plane $x\geq 0$.

  * •

Every edge $e\in E_{\mathsf{cross}}(G)$ crosses the line $x=0$ exactly once,
at $(0,Y_{e})$, where $Y_{e}<0$ or $Y_{e}>n-1$.

Figure 8(a) presents an example of a graph, and of a plane drawing of it which
satisfies the above properties. Note that the above plane drawing crucially
uses the fact that the line $x=0$ partitions the plane into two half-planes
($x\leq 0$ and $x\geq 0$). Now, let us move on to item (b).

The construction of $H$ from $G$ is done as follows. For each edge
$e=v_{i}v_{j}\in E_{\mathsf{cross}}(G)$, we add a new vertex
$\mathsf{new}_{e}$ to the graph, represented by the point $(0,Y_{e})$.
Consequently, the edge $e=v_{i}v_{j}$ is replaced by two edges
$v_{i}\mathsf{new}_{e}$ and $\mathsf{new}_{e},v_{j}$. One of those edges is in
$E_{\mathsf{left}}(H)$ and the other is in $E_{\mathsf{right}}(H)$. Therefore,
the vertex $\mathsf{new}_{e}$ is a subdivision vertex of the edge $e$. More
formally,

$\displaystyle V(H)$ $\displaystyle=V(G)\cup\\{\mathsf{new}_{e}\mid e\in
E_{\mathsf{cross}}(G)\\};$ $\displaystyle E(H)$
$\displaystyle=E_{\mathsf{left}}(G)\cup
E_{\mathsf{right}}(G)\cup\\{x\mathsf{new}_{e},\mathsf{new}_{e}y\mid e=xy\in
E_{\mathsf{cross}}(G)\\}.$

What did this achieve for us? The graph $H$ has some nice properties, which we
mentioned in item (c), and will elaborate now.

  * •

$H$ is a subdivision of $G$. Edges of $E_{\mathsf{left}}(G)$ and
$E_{\mathsf{right}}(G)$ are retained as-is in $H$, and edges of
$E_{\mathsf{cross}}(G)$ are subdivided once.

  * •

$H$ is a planar graph. This is because $G$ is a planar graph, and subdivision
does not affect planarity.

  * •

No edge of $H$ crosses the y-axis ($E_{\mathsf{cross}}(H)=\emptyset$). This is
a straightforward feature of our construction.

  * •

$n\leq n_{H}\leq 4n$, where $n_{H}=|V(H)|$. This is because $G$ has at most
$3n$ edges (as $G$ is planar), and each edge of $G$ is subdivided at most once
in $H$. Since $H$ also retains the vertices of $G$, $n_{H}\leq n+3n$.

From $H$, we construct
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, as described in
Section 3.1. Then we progressively build its StabGIG representation (item
(d)). We first define the positions of the segments corresponding to the apex
vertex of $H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ and the
original vertices of $H$ in our StabGIG representation of
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ . Note that the apex
vertex in $H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is called
$a$, just as the apex vertex in
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, since these vertices
finally coincide in our construction.

The vertices with the minimum and maximum y-coordinates in $H$ are at
$(0,Y_{\min})$ and $(0,Y_{\max})$, where

$\displaystyle Y_{\min}$
$\displaystyle=\operatorname{min}\left(\\{0\\}\cup\\{Y_{e}\mid e\in
E_{\mathsf{cross}}(G)\\}\right);$ $\displaystyle Y_{\max}$
$\displaystyle=\operatorname{max}\left(\\{n-1\\}\cup\\{Y_{e}\mid e\in
E_{\mathsf{cross}}(G)\\}\right).$

We may assume that $Y_{\min}=0$ and $Y_{\max}=n_{H}-1$, and that the other
vertices of $H$ can be shifted accordingly so that their coordinates are
$(0,0),(0,1),(0,2),\ldots,(0,n_{H}-1)$.666This can be done, for example, by
shifting the x-axis downwards and making the gap between consecutive points as
$1$. Furthermore, the vertices are suitably renamed as
$w_{1},w_{2},w_{3},\ldots,w_{n_{H}}$ so that each $w_{i}$ has the coordinate
$(0,i-1)$. For each vertex $x\in
V(H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}})$, let $\mathtt{c}(x)$
be its corresponding segment. See Figure 10.

The apex vertex $a$ of
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$:
$\displaystyle\mathtt{c}(a)=[(0,0),(0,n_{H}-1)]$ The original vertices of $H$:
$\displaystyle\mathtt{c}(w_{i})=[(-i-0.1,i-1),(2n_{H}-i+0.1,i-1)]\qquad\forall\,i\in[n_{H}].$

$\epsilon
d_{I}$$-i+0.01$$\mathtt{c}(u_{e}^{1})$$x$-axis$w_{i}(0,i-1)$$w_{j}(0,j-1)$$(2n_{H}-j+0.1,j-1)$$y$-axis$\epsilon
d_{I}$$\mathtt{c}(u_{e}^{2})$$-j-0.01$$(-j-0.1,j-1)$$(-j,j-1)$$(-i-0.1,i-1)$$(-i,i-1)$$\mathtt{c}(w_{j})$$(2n_{H}-i+0.1,i-1)$$\mathtt{c}(w_{i})$$(\mathbf{j}_{e},\mathbf{j}_{e})$$(\mathbf{i}_{e},\mathbf{j}_{e})$$\mathtt{c}(u_{e}^{3})$$\mathtt{c}(a)$$\ell$$-j+0.01$$-i-0.01$

Figure 10: StabGIG representation of the path
$(w_{i},u_{e}^{1},u_{e}^{2},u_{e}^{3},w_{j})$ of
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ corresponding to the
edge $e=w_{i}w_{j}$ of $H$, with $i<j$.

We fix the line $y=x$ as our stab line $\ell$ (recall that $\ell$ does not
need to be axis-parallel). It is easy to see that all the segments described
so far intersect the stab line. This brings us to item (e), where we need to
place the segments corresponding to the three subdivision vertices of $e$ for
each edge $e$ of $H$.

Let us consider edges of $E_{\mathsf{left}}(H)$. Later, we will deal with
edges of $E_{\mathsf{right}}(H)$. We construct a set of intervals
$\mathfrak{I}_{\mathsf{left}}$ from $E_{\mathsf{left}}(H)$ as follows. For
each edge $e=w_{i}w_{j}\in E_{\mathsf{left}}(H)$ (where $i<j$), the set
$\mathfrak{I}_{\mathsf{left}}$ contains an open interval $(i-1,j-1)$. Thus,
the number of intervals in $\mathfrak{I}_{\mathsf{left}}$ is the number of
edges in $E_{\mathsf{left}}(H)$. Now, note that $\mathfrak{I}_{\mathsf{left}}$
has the following interesting property.

######  Observation 10.

If two intervals of $\mathfrak{I}_{\mathsf{left}}$ have an overlap (i.e., the
intervals are not disjoint), then one of them must be contained in the other.

Observation 10 is well known and easy to see; it is the basic underlying
principle of _book thickness_ or _book embeddings_ of graphs (for a proof, see
[6]). We will use this observation crucially in our construction of the three
subdivision segments for each edge $e$ of $E_{\mathsf{left}}(H)$.

Given an interval $I\in\mathfrak{I}_{\mathsf{left}}$, let its _depth_ ,
denoted by $\mathsf{d}_{I}$, be the number of intervals $I^{\prime}\in
E_{\mathsf{left}}(H)$ such that $I\subseteq I^{\prime}$. In other words,
$\mathsf{d}_{I}$ is the number of intervals that contain $I$ (including $I$
itself). Thus, $1\leq\mathsf{d}_{I}\leq n_{H}-1$. Now we are ready to describe
our construction.

Fix $\varepsilon=0.01/n_{H}$. Let $e=w_{i}w_{j}\in E_{\mathsf{left}}(H)$ such
that $i<j$. Let $I=(i-1,j-1)$ be the interval corresponding to $e$ in
$\mathfrak{I}_{\mathsf{left}}$. After the $3$-subdivision, the edge $e$
becomes the path $(w_{i},u_{e}^{1},u_{e}^{2},u_{e}^{2},w_{j})$ in
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$. We already know the
coordinates of the segments for $w_{i}$ and $w_{j}$. As for the other three
segments, we define $\mathbf{j}_{e}$ and $\mathbf{i}_{e}$ as follows.

$\displaystyle\mathbf{j}_{e}$ $\displaystyle=-j+\varepsilon\mathsf{d}_{I};$
$\displaystyle\mathbf{i}_{e}$ $\displaystyle=-i-\varepsilon\mathsf{d}_{I}.$

Now, we are set to define the coordinates of the other three subdivision
segments of $e$, which draw a $\sqcup$-shape. See Figure 10.

$\displaystyle\mathtt{c}(u_{e}^{3})$
$\displaystyle=\left[(\mathbf{j}_{e},j-1),(\mathbf{j}_{e},\mathbf{j}_{e})\right];$
$\displaystyle\mathtt{c}(u_{e}^{2})$
$\displaystyle=\left[(\mathbf{j}_{e},\mathbf{j}_{e}),(\mathbf{i}_{e},\mathbf{j}_{e})\right];$
$\displaystyle\mathtt{c}(u_{e}^{1})$
$\displaystyle=\left[(\mathbf{i}_{e},\mathbf{j}_{e}),(\mathbf{i}_{e},i-1)\right].$

Before proving that the 3 segments do not intersect any segments apart from
$w_{i}$, $w_{j}$, and each other, let us prove that all 3 segments intersect
the stab line. Consider the point of intersection of $\mathtt{c}(u_{e}^{3})$
and $\mathtt{c}(u_{e}^{2})$, namely $(\mathbf{j}_{e},\mathbf{j}_{e})$. This
point has the same x- and y-coordinate, and so it lies on the stab line $y=x$.
Thus, all that remains to be shown is that $\mathtt{c}(u_{e}^{1})$ also
intersects the stab line. Since $i\leq j-1$ and
$\varepsilon\mathsf{d}_{I}<0.01$,

$\mathbf{j}_{e}\leq\mathbf{i}_{e}\leq i-1.$

Hence, the point $(\mathbf{i}_{e},\mathbf{i}_{e})$ lies on the segment
$\mathtt{c}(u_{e}^{1})=\left((\mathbf{i}_{e},\mathbf{j}_{e}),(\mathbf{i}_{e},i-1)\right)$,
and on the stab line $y=x$ also.

Now, we will show that for two edges $e=w_{i}w_{j}$ (where $i<j$) and
$e^{\prime}=w_{i^{\prime}}w_{j^{\prime}}$ (where $i^{\prime}<j^{\prime}$) of
$E_{\mathsf{left}}(H)$, the segments corresponding to the three subdivision
vertices of $e$ do not intersect the segments corresponding to the three
subdivision vertices of $e^{\prime}$. Let their corresponding intervals in
$\mathfrak{I}_{\mathsf{left}}$ be $I$ and $I^{\prime}$, respectively. Due to
Observation 10, we have only two cases.

  1. 1.

Case 1: $I$ and $I^{\prime}$ are disjoint. Suppose that $i<j\leq
i^{\prime}<j^{\prime}$ (the other sub-case, $i^{\prime}<j^{\prime}\leq i<j$,
is similar). We have the following.

$\displaystyle i<j$ $\displaystyle\leq i^{\prime}<j^{\prime}$
$\displaystyle-j^{\prime}<-i^{\prime}$ $\displaystyle\leq-j<-i$
$\displaystyle-j^{\prime}+\varepsilon\mathsf{d}_{I^{\prime}}<-i^{\prime}-\varepsilon\mathsf{d}_{I^{\prime}}$
$\displaystyle<-j+\varepsilon\mathsf{d}_{I}<-i-\varepsilon\mathsf{d}_{I}$
(since $2\varepsilon\mathsf{d}_{I^{\prime}}<1\leq j^{\prime}-i^{\prime}$ and
$2\varepsilon\mathsf{d}_{I}<1\leq j-i$)
$\displaystyle\mathbf{j}_{e^{\prime}}<\mathbf{i}_{e^{\prime}}$
$\displaystyle<\mathbf{j}_{e}<\mathbf{i}_{e}$

Thus, the x-coordinate of each of the 3 subdivision segments of $e^{\prime}$
is at most $\mathbf{i}_{e^{\prime}}$, and the x-coordinate of each of the 3
subdivision segments of $e$ is at least $\mathbf{j}_{e}$. This completes the
proof of Case 1.

  2. 2.

Case 2: One of $I$ or $I^{\prime}$ contains the other. Suppose that
$I\subseteq I^{\prime}$ (the other sub-case, $I^{\prime}\subseteq I$, is
similar). Then, note that $\mathsf{d}_{I^{\prime}}<\mathsf{d}_{I}$. We have
the following.

$\displaystyle i^{\prime}\leq i$ $\displaystyle<j\leq j^{\prime}$ (since
$I\subseteq I^{\prime}$) $\displaystyle-j^{\prime}\leq-j$
$\displaystyle<-i\leq-i^{\prime}$
$\displaystyle-j^{\prime}+\varepsilon\mathsf{d}_{I^{\prime}}<-j+\varepsilon\mathsf{d}_{I}$
$\displaystyle<-i-\varepsilon\mathsf{d}_{I}<-i^{\prime}-\varepsilon\mathsf{d}_{I^{\prime}}$
(since $\mathsf{d}_{I^{\prime}}<\mathsf{d}_{I}$ and
$2\varepsilon\mathsf{d}_{I}<1\leq j-i$)
$\displaystyle\mathbf{j}_{e^{\prime}}<\mathbf{j}_{e}$
$\displaystyle<\mathbf{i}_{e}<\mathbf{i}_{e^{\prime}}$

Thus, the x-coordinate of $\mathtt{c}(u_{e^{\prime}}^{3})$ (namely
$\mathbf{j}_{e^{\prime}}$) is less than the x-coordinate of each of the 3
subdivision segments of $e$, and the x-coordinate of
$\mathtt{c}(u_{e^{\prime}}^{1})$ (namely $\mathbf{i}_{e^{\prime}}$) is greater
than the x-coordinate of each of the 3 subdivision segments of $e$. Finally,
the y-coordinate of $\mathtt{c}(u_{e^{\prime}}^{2})$ (namely
$\mathbf{j}_{e^{\prime}}$) is less than the y-coordinate of each of the 3
subdivision segments of $e$. This completes the proof of Case 2.

This completes the construction of the StabGIG representation for the subgraph
of $H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ induced by the
original vertices of $H$, the apex vertex $a$ and the subdivision vertices
located in the left half-plane. For the vertices and edges located in the
right half-plane, the construction is similar but replaces the $\sqcup$-shapes
by $\sqcap$-shapes. The correctness of our construction follows from Cases 1
and 2 above.

####  3.2.3 StabGIG representation of
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$

In order to conclude our proof of Proposition 9, we need – according to item
(f) – to convert the StabGIG representation of
$H_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ into a StabGIG
representation of $G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, for
an arbitrary $k\geq 7$. This operation reduces to further subdividing one edge
of $H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, that may be
appropriately chosen, by transforming it into a path of odd length $2h+1$, for
an appropriate integer $h\geq 1$.

Consider the StabGIG representation of
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$. For each edge $e\in
E_{\mathsf{cross}}(G)$, a 7-subdivision is performed in
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$. But for each edge
$e\in E_{\mathsf{left}}(G)\cup E_{\mathsf{right}}(G)$, only a 3-subdivision is
performed in $H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$. When
$k=7$, the latter edges are insufficiently subdivided in
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ with respect to
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$. Moreover, when $k>7$
all the original edges in $G$ are insufficiently subdivided. In all cases, let
$e\in E(G)$ be one of the edges that are insufficiently subdivided, and assume
that $e\in E_{\mathsf{left}}(H)$. (Otherwise, when $e\in
E_{\mathsf{right}}(H)$ the approach is similar, whereas when $e\in
E_{\mathsf{cross}}(G)$ we have to perform the same approach on the ’half-edge’
of $e$ that belongs to $E_{\mathsf{left}}(H)$.) In
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, $e$ is 3-subdivided.
Assume we need a $k$-subdivision of $e$, with odd $k\geq 7$, and let
$h=(k-3)/2$. Then we perform a $2h$-subdivision of the edge
$u_{e}^{1}u_{e}^{2}$ of
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, and describe below
the new segments representing $u_{e}^{1},u_{e}^{2}$ and the $2h$ supplementary
vertices.

In $H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, the intersection
point between the segments $\mathtt{c}(u_{e}^{3})$ and $\mathtt{c}(u_{e}^{2})$
is $(\mathbf{j}_{e},\mathbf{j}_{e})$. The closest possible similar point
located on the stab line towards right is the point
$(\mathbf{j}_{e}+\varepsilon,\mathbf{j}_{e}+\varepsilon)$. We then replace the
segment $\mathtt{c}(u_{e}^{2})$ with a succession of $2h+1$ alternating
horizontal and vertical segments whose intersections define the path required
by the $2h$-subdivision of $(u_{e}^{1},u_{e}^{2})$. See Figure 11.

Figure 11: Replacement of $\mathtt{c}(u_{e}^{2})$ (left), for some edge $e$
which is not sufficiently subdivided in
$H_{3\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$, with a sequence of
segments describing a path of length $2h+1$ (right). In this figure, $h=2$.
The dotted $\sqcup$-shape indicates the closest possible location of an
$\sqcup$-shape located above the one we defined for $e$.

Formally, let $\varepsilon_{2}=\varepsilon/(h+1)$, and define the following
segments. The horizontal segment obtained for $h=0$ is the new segment
$\mathtt{c}(u_{e}^{2})$.

For $0\leq t\leq h-1$:

$\left[(\mathbf{j}_{e}+t\varepsilon_{2},\mathbf{j}_{e}+t\varepsilon_{2}),(\mathbf{j}_{e}+(t+1)\varepsilon_{2},\mathbf{j}_{e}+t\varepsilon_{2})\right]$
$\left[(\mathbf{j}_{e}+(t+1)\varepsilon_{2},\mathbf{j}_{e}+t\varepsilon_{2}),(\mathbf{j}_{e}+(t+1)\varepsilon_{2},\mathbf{j}_{e}+(t+1)\varepsilon_{2})\right]$

Complete this set of segments with:

$\left[(\mathbf{j}_{e}+h\varepsilon_{2},\mathbf{j}_{e}+h\varepsilon_{2}),(\mathbf{i}_{e},\mathbf{j}_{e}+h\varepsilon_{2})\right]$
$\mathtt{c}(u_{e}^{1})=\left[(\mathbf{i}_{e},\mathbf{j}_{e}+h\varepsilon_{2}),(\mathbf{i}_{e},i-1)\right]$

All the segments corresponding to the $2h$ new subdivision vertices lie
strictly below the closest upper segment not involved in the subdivision of
$e$ (whose $y$-coordinate is at least $\mathbf{j}_{e}+\varepsilon$), and (not
strictly) above the former segment $\mathtt{c}(u_{e}^{2})$. They also lie
between the $x$-coordinates of $\mathtt{c}(u_{e}^{3})$ and
$\mathtt{c}(u_{e}^{1})$. Thus they cannot intersect other segments. So we have
representation of the path with $(2h+1)$ edges required by the subdivision.

This ends the proof of Proposition 9.

####  3.2.4 Proof of Theorem 2

For a given graph $\Gamma$, recall (see Section 2.2) that $\Gamma+x$ is the
graph obtained by adding to $\Gamma$ a universal vertex $x$. In order to show
that StabGIGRec belongs to NP, note that a grid representation of $\Gamma$ in
which all the segments are stabbed by the same line $\ell$ may be seen as a
representation in the plane of $\Gamma+x$ with segments following at most
three directions ($x$ is represented by the stab line $\ell$, that is replaced
in this representation with a long segment). This remark allows us to invoke
once again the result in [20], which guarantees that since the number of
directions of the segments in the representation is fixed, StabGIGRec is in
NP.

Furthermore, $G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is
obtained in polynomial time from $G$. According to Observation 7 with fixed
$k\geq 7$ and $g=k+3$, the girth of
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ equals $g$. It remains
to show that $G$ is a yes-instance of PHPC if and only if
$G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is a yes-instance of
StabGIGRec. Proposition 9 shows the forward direction.

For the backward direction, we first show – seeking to use Proposition 8 –
that if $G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is a StabGIG,
then $G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is a 1-string
graph. To this end, it is sufficient to note that each segment in a grid
representation of $G_{k\operatorname{-{\mathsf{div}}}}^{\mathsf{\;apex}}$ is a
1-string, and that two segments that intersect without crossing (because an
enpoint of one segment lies on the second segment) may be easily transformed
into two crossing segments. Now, using Proposition 8, we deduce that $G$ is a
yes-instance of PHPC.

##  4 Conclusion

In this paper, we proved that recognizing grounded └-graphs is $\NP$-complete.
A natural direction of research would be to find interesting subclasses of
grounded └-graphs with polynomial time recognition algorithms. One such
candidate class could be the _grounded unit └-graphs_. An unit └-shape is a
made by joining the bottom end-point of a vertical ($|$) segment (of arbitrary
length) to the left end-point of a horizontal ($-$) segment of _unit_ length.
Grounded unit └-graphs are the intersection graphs of unit └-shapes such that
all the └-shapes’ anchors lie on the same horizontal line. Grounded unit
└-graphs is a subclass of _cocomparability_ graphs and contains _unit
interval_ graphs and _permutation graphs_ as its subclasses. The above
discussion motivates the following question.

######  Question 1.

What is the computational complexity of recognizing grounded unit └-graphs?

In this paper, we proved that recognizing stabbable grid intersection graphs
is $\NP$-complete even when the inputs are restricted to apex graphs, a graph
class that does not contain $K_{6}$ as a minor. In contrast, recognizing
$K_{4}$-minor free stabbable grid intersection graphs is trivial (since
$K_{4}$-minor free graphs are planar and all planar bipartite graphs are
stabbable grid intersection graphs). This motivates the following question.

######  Question 2.

What is the computational complexity of recognizing $K_{5}$-minor free
stabbable grid intersection graphs?

Theorem 2 implies that StabGIGRec is not FPT (fixed-parameter tractable), when
parameterized by the _apex number_ of the graph, that is, the minimum number
of vertices required to be removed to make the resultant graph planar. But our
reduction procedure results in graphs with large maximum degree. On the other
hand, a result of Mustaţă & Pergel [24], implies that recognizing many
geometric intersection graph classes (e.g. string graphs, $1$-string graphs)
remain $\NP$-hard even if the maximum degree of the input graph is bounded by
a constant. Therefore, recognition of such graph classes does not admit FPT
with respect to the maximum degree. But the graphs produced by their reduction
procedure have large apex number. Therefore, the following question arises.

######  Question 3.

Is StabGIGRec FPT w.r.t sum of maximum degree and apex number?

## References

  * [1] Pankaj K Agarwal, Marc Van Kreveld, and Subhash Suri.  Label placement by maximum independent set in rectangles.  Computational Geometry, 11(3-4):209–218, 1998.
  * [2] Andrei Asinowski, Elad Cohen, Martin Charles Golumbic, Vincent Limouzy, Marina Lipshteyn, and Michal Stern.  Vertex intersection graphs of paths on a grid.  J. Graph Algorithms Appl., 16(2):129–150, 2012.
  * [3] E Asplund and B Grünbaum.  On a coloring problem.  MATHEMATICA SCANDINAVICA, 8:181–188, 1960.
  * [4] C. Auer and A. Gleißner.  Characterizations of deque and queue graphs.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 35–46. Springer, 2011.
  * [5] Seymour Benzer.  On the topology of the genetic fine structure.  Proceedings of the National Academy of Sciences, 45(11):1607–1620, 1959.
  * [6] Frank Bernhart and Paul C Kainen.  The book thickness of a graph.  Journal of Combinatorial Theory, Series B, 27(3):320–331, 1979\.
  * [7] Prosenjit Bose, Paz Carmi, J Mark Keil, Anil Maheshwari, Saeed Mehrabi, Debajyoti Mondal, and Michiel Smid.  Computing maximum independent set on outerstring graphs and their relatives.  Computational Geometry, 103:101852, 2022.
  * [8] Dibyayan Chakraborty, Sandip Das, and Joydeep Mukherjee.  On dominating set of some subclasses of string graphs.  Computational Geometry, 107:101884, 2022.
  * [9] Dibyayan Chakraborty and Kshitij Gajjar.  Finding geometric representations of apex graphs is np-hard.  In International Conference and Workshops on Algorithms and Computation, pages 161–174. Springer, 2022.
  * [10] Steven Chaplick, Stefan Felsner, Udo Hoffmann, and Veit Wiechert.  Grid intersection graphs and order dimension.  Order, 35(2):363–391, 2018.
  * [11] F. Chung, F. T. Leighton, and A. Rosenberg.  Diogenes: A methodology for designing fault-tolerant VLSI processor arrays.  Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Microsystems Program Office, 1983.
  * [12] Fan RK Chung, Frank Thomson Leighton, and Arnold L Rosenberg.  Embedding graphs in books: a layout problem with applications to vlsi design.  SIAM Journal on Algebraic Discrete Methods, 8(1):33–58, 1987.
  * [13] James Davies, Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak.  Grounded L-graphs are polynomially $\chi$-bounded.  arXiv preprint arXiv:2108.05611, 2021.
  * [14] Stefan Felsner.  Rectangle and square representations of planar graphs.  In Thirty essays on geometric graph theory, pages 213–248. Springer, 2013.
  * [15] Daniel Gonçalves, Lucas Isenmann, and Claire Pennarun.  Planar graphs as L-intersection or L-contact graphs.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 172–184, 2018.
  * [16] András Gyárfás and Jenö Lehel.  Covering and coloring problems for relatives of intervals.  Discrete Mathematics, 55(2):167–180, 1985.
  * [17] I. B. Hartman, I. Newman, and R. Ziv.  On grid intersection graphs.  Discrete Mathematics, 87(1):41–52, 1991.
  * [18] Vít Jelínek and Martin Töpfer.  On grounded L-graphs and their relatives.  The Electronic Journal of Combinatorics, pages P3–17, 2019.
  * [19] J. Kratochvíl.  A special planar satisfiability problem and a consequence of its NP-completeness.  Discrete Applied Mathematics, 52(3):233–252, 1994.
  * [20] Jan Kratochvíl and Jirí Matousek.  Intersection graphs of segments.  Journal of Combinatorial Theory, Series B, 62(2):289–315, 1994\.
  * [21] F. Kuhn, R. Wattenhofer, and A. Zollinger.  Ad hoc networks beyond unit disk graphs.  Wireless Networks, 14(5):715–729, 2008.
  * [22] C Lekkeikerker and Johan Boland.  Representation of a finite graph by a set of intervals on the real line.  Fundamenta Mathematicae, 51:45–64, 1962.
  * [23] Sean McGuinness.  On bounding the chromatic number of L-graphs.  Discrete Mathematics, 154(1-3):179–187, 1996.
  * [24] I. Mustaţă and M. Pergel.  On unit grid intersection graphs and several other intersection graph classes.  Acta Mathematica Universitatis Comenianae, 88(3):967–972, 2019\.
  * [25] Irena Rusu.  On the complexity of recognizing Stick graphs.  preprint arXiv:2205.09076, 2022.
  * [26] N. A. Sherwani.  Algorithms for VLSI Physical Design Automation.  Springer US, 2007.
  * [27] D. M. Thilikos and H. L. Bodlaender.  Fast partitioning L-apex graphs with applications to approximating maximum induced-subgraph problems.  Information processing letters, 61(5):227–232, 1997.
  * [28] D. J. A. Welsh.  Knots and braids: some algorithmic questions.  Contemporary Mathematics, 147, 1993.
  * [29] J. Xu and B. Berger.  Fast and accurate algorithms for protein side-chain packing.  Journal of the ACM (JACM), 53(4):533–557, 2006.


11institutetext: John Adams Institute for Accelerator Science, The Blackett
Laboratory, Imperial College London, UK

# Laser Wakefield Accelerators

Z. Najmudin

###### Abstract

The one-dimensional wakefield generation equations are solved for increasing
levels of non-linearity, to demonstrate how they contribute to the overall
behaviour of a non-linear wakefield in a plasma. The effect of laser guiding
is also studied as a way to increase the interaction length of a laser
wakefield accelerator.

Keywords
Laser; wakefield; accelerator; guiding.

##  0.1 Introduction

Large amplitude relativistic plasma waves, driven in the wake of a
relativistic driver passing through a plasma, are a potential linear
accelerator system [1]. This is commonly called a wakefield accelerator. The
plasma, being already ionized, can support accelerating fields many orders of
magnitude greater than in conventional accelerators. Indeed, at the time of
writing, reports of energy gains of ${\sim}1\UGeV$ in distances of centimetres
are now becoming common [2, 3, 4, 5].

Possible drivers of the relativistic plasma wave include light [1], electron
[6], positron [7], or proton beams [8]. A generalized one-dimensional (1D)
wakefield generation equation describing generation by all of the mentioned
drivers is [9]

$\frac{1}{{k_{\mathrm{p}}}^{2}}\frac{\partial^{2}\phi}{\partial\zeta^{2}}=\pm\frac{n_{\mathrm{b}}}{n_{0}}+{\gamma_{\mathrm{p}}}^{2}\left\\{\beta_{\mathrm{p}}\left[1-\frac{(1+a^{2})}{{\gamma_{\mathrm{p}}}^{2}(1+\phi)^{2}}\right]^{-1/2}-1\right\\},$
(1)

where the potential $\phi$ is normalized to $mc^{2}/e$ and the variations are
in the quasi-static frame with $\zeta\leavevmode\nobreak\
=\leavevmode\nobreak\ z-v_{\mathrm{p}}t$ for a driver of velocity
$v_{\mathrm{p}}$. The first term on the right describes the response to a
particle beam driver and is $+$ for an electron and $-$ for a positively
charged driver. In its absence ($n_{\mathrm{b}}=0$), and in the limit that the
phase velocity of the wave $\gamma_{\mathrm{p}}\gg 1$, then expanding the
square brackets and also expanding
$\beta_{\mathrm{p}}=(1-\frac{1}{{\gamma_{\mathrm{p}}}^{2}})^{1/2}$ gives a
non-linear laser wakefield driver equation:

$\frac{1}{{k_{\mathrm{p}}}^{2}}\frac{\partial^{2}\phi}{\partial\zeta^{2}}=\frac{1}{2}\left[\frac{(1+a^{2})}{(1+\phi)^{2}}-1\right].$
(2)

In the small amplitude limit, $\phi\ll 1$, this can be further simplified to

$\left(\frac{\partial^{2}}{\partial\zeta^{2}}+k_{\mathrm{p}}{{}^{2}}\right)\phi=\frac{1}{2}{k_{\mathrm{p}}}^{2}a^{2},$
(3)

which reveals itself to be a driven oscillator. Below, we obtain eqn:driven
starting from the linear forms of the fluid equations of motion, continuity
and Gauss’s Law. The electric field and density can then be obtained from
${\bf E}=-\nabla\phi$ and Poisson’s equation. This allows us to obtain some of
the common characteristics of a laser driven wakefield accelerator. By adding
further levels of non-linearity, we reveal some of the behaviour of laser
wakefield accelerators in the non-linear regime.

##  0.2 Laser wakefield

###  0.2.1 Basic equations

Beginning with Gauss’s Law, and the continuity and fluid motion equations for
electrons in a plasma in one dimension (the ions are assumed to be heavy and
thus fixed) subject to a laser of peak intensity $I$ and wavelength $\lambda$
with a normalized vector potential $a={eE}/{m\omega c}\approx 8.9\times
10^{-6}\left(I\lambda^{2})\right)^{0.5}$ [SI units]:

$\epsilon_{0}\frac{\partial E}{\partial
z}=-e(n_{\mathrm{e}}-n_{\mathrm{i}}),\quad\frac{\partial
n_{\mathrm{e}}}{\partial t}+\frac{\partial}{\partial
z}{(n_{\mathrm{e}}v)}=0,\quad\left[\frac{\partial p}{\partial
t}+v\frac{\partial p}{\partial
z}\right]=-eE+\frac{1}{\gamma_{\perp}}mc^{2}\frac{\partial(a^{2})}{\partial
z},$

where $p=\gamma mv$ is the momentum of the fluid element. Note that the last
term on the right of the equation of motion is the relativistic ponderomotive
force, with the relativistic factor due to the quiver motion usually given by
$\gamma_{\perp}=\sqrt{1+(a^{2}/2)}$ for linear polarization. It is this
ponderomotive force which mediates the interaction between laser and plasma.

For simplicity, we use normalized units: $\epsilon_{0},e,m,c=1$. We also move
to the frame in which the laser driver is stationary (the quasistatic
approximation), i.e. $\zeta=z-v_{\mathrm{p}}t\approx z-ct$. So
$\frac{\partial}{\partial z}=\frac{\partial}{\partial\zeta}$ and
$\frac{\partial}{\partial t}=-c\frac{\partial}{\partial\zeta}$. Also using
$n_{\mathrm{e}}=n_{0}+n_{1}$, where $n_{0}$ is the initial plasma density and
$n_{1}$ is therefore the amplitude of the plasma wave, the above equations
become

$\frac{\partial E}{\partial\zeta}=-n_{1},\quad
n_{1}=(n_{0}+n_{1})\beta,\quad(1-\beta)\frac{\partial
p}{\partial\zeta}=E-\frac{1}{\gamma_{\perp}}\frac{\partial(a^{2})}{\partial\zeta}.$
(4)

Here $\beta=v/c$ and is given by

$\beta=\frac{p}{(1+p^{2}+a^{2})^{1/2}},$

i.e. the relativistic factor of the electrons depends on not only their
longitudinal motions but also their transverse oscillations, which at the
intensities used to drive laser wakefield accelerators are also relativistic.

Starting from these base equations, we can now consider different levels of
non-linearity and assess their effect on wakefield generation.

###  0.2.2 Linear wakes

(a) (b) (c)

Figure 1: Linear wakefield generation: plots of $E/E_{0}$, $v/c$, and
$n_{\mathrm{e}}/n_{0}$ (in blue) for laser pulse $a=a_{0}\sin(\pi\zeta/L)$
with pulse length
$L={\rm(a)}\,\frac{1}{2},{\rm(b)}\,1,{\rm(c)}\,2\,\lambda_{\mathrm{p}}$ and
$a_{0}=0.2$ (in red).

For small amplitudes, we can assume, $n_{1}\ll n_{0}$, $\beta\ll 1$,
$\gamma=1$ and $p=mc\beta$:

$\frac{\partial E}{\partial\zeta}=-n_{1},\quad
n_{1}=n_{0}\beta,\quad\frac{\partial\beta}{\partial\zeta}=E-\frac{\partial(a^{2})}{\partial\zeta}.$

Combining these equations gives us essentially eqn:linear, with (in normalized
units) $k_{\mathrm{p}}{{}^{2}}=n_{0}$. For a normalized laser intensity
profile $a^{2}=a_{0}{{}^{2}}\sin^{2}(\pi\zeta/L)$ for $0<\zeta<L$, i.e. a half
sinusoid, the wake growth is optimized for $L=\lambda_{\mathrm{p}}\equiv
2\pi/k_{\mathrm{p}}$, or alternatively, when the intensity full-width half-max
$L_{\mathrm{fwhm}}=\lambda_{\mathrm{p}}/2$. This can be seen in denScan where
these equations have been solved numerically using the scipy.integrate.odeint
function in python. One can see that the plasma wave grows at the front end of
the laser pulse as the ponderomotive force pushes electrons ahead of it, which
then relax to form a plasma oscillation. When resonant, the back of the pulse
gives an extra ponderomotive kick to the plasma wave growing it to higher
amplitude. At resonance, the wake trailing (behind) the laser pulse has
solution

$n_{\mathrm{e}}=n_{0}\left(1+\frac{\pi}{4}a_{0}{{}^{2}}\sin
k_{\mathrm{p}}\zeta\right),\qquad E_{z}=E_{0}\frac{\pi}{4}a_{0}{{}^{2}}\cos
k_{\mathrm{p}}\zeta,\qquad\phi=-\frac{mc^{2}}{e}\frac{\pi}{4}a_{0}{{}^{2}}\sin
k_{\mathrm{p}}\zeta,$

where $E_{0}=(mc\omega_{\mathrm{p}}/e)$ is the electric field for sinusoidal
oscillations of maximum amplitude, i.e. for $n_{1}=n_{0}$. For yet longer
pulse lengths, the wakefield (the plasma wave amplitude following the laser
pulse) reduces again, to the point where for $L=2\lambda_{\mathrm{p}}$, there
is no wakefield at all. There is however a driven (or forced) oscillation of
the plasma wave whilst the laser pulse is still active (see denScan(c)), which
may be useful if only a single bunch needs to be accelerated, rather than a
pulse train. There are also smaller amplitude resonances for
$L\approx(n+\frac{1}{2})\lambda_{\mathrm{p}}$ for integer $n>2$.

Clearly there is a problem for linear solutions with $a_{0}>1$, where
$n_{\mathrm{e}}$ can become negative. In fact, in the fluid model, electron
sheets would cross, so that instead of seeing a returning force, some
electrons end up being continually accelerated, a process called
‘wavebreaking’ [10]. Wavebreaking is interesting because it suggests that
plasma electrons can themselves be a source of particles to be accelerated in
the accelerator [11]. Thus, this cold linear wavebreaking limit for the
electric field $E_{0}=(mc\omega_{\mathrm{p}}/e)$ is useful for giving an
estimate of the energy output from the accelerator. In the laser driven case,
the wakefield travels at the group velocity of the driving pulse, as
quantified by $\gamma_{\mathrm{ph}}\approx(\omega_{0}/\omega_{\mathrm{p}})$
for a laser of angular frequency $\omega_{0}$. The maximum energy gain is then
given by

$W_{\mathrm{max}}\approx 2\gamma_{\mathrm{ph}}{{}^{2}}mc^{2},$

and so is dependent on the plasma density. Interestingly, lower density
(smaller $\omega_{\mathrm{p}}$, thus higher $\gamma_{\mathrm{ph}}$) results in
greater energy gain. This, however, comes at the expense of the greater laser
energy that is required to drive the larger sized wakefield that results from
lower density.

###  0.2.3 Non-linear wakes

For $n_{1}\sim n_{0}$, the continuity equation gives
$n_{1}=n_{0}(1-\beta)^{-1}$. Since in their fluid motion, the electrons have
$-1<\beta<1$, one can see that $\frac{1}{2}<n_{1}/n_{0}<\infty$. Because of
this non-linearity in the continuity equation, the lowest density in a 1D wake
cannot be less than $\frac{1}{2}n_{0}$. The plasma wave as a result becomes
non-linearly steepened, with sharp high-density spikes associated with longer
areas of lower electron density plasma. Of course this is only true in one
dimension. In three dimensions, at high $a_{0}$, transverse motion can lead to
$n_{\mathrm{e}}\rightarrow 0$, or cavitation. Relativistic effects in the
equation of motion add further non-linearity, as in eqn:nonlinear. The effect
of these non-linearities can be seen in aScan, for a half sinusoidal laser
pulse (as before) with $L=\lambda_{\mathrm{p}}$, and increasing laser strength
$a_{0}$.

(a) (b) (c)

Figure 2: Non-linear wakefield generation: plots of $E/E_{0}$, $v/c$, and
$n_{\mathrm{e}}/n_{0}$ (in blue) for laser pulse $a=a_{0}\sin(\pi\zeta/L)$
with $a_{0}={\rm(a)}\,0.5,{\rm(b)}\,1.0$ and ${\rm(c)}\,1.5$ (in red).

Even for $a_{0}=0.5$ (aScan(a)), the density profiles of the plasma wave have
begun to be non-linearly steepened. This is particularly clear for
$a_{0}=1.0,1.5$ (aScan(b,c)), where the plasma wave consists of sharp density
spikes either side of shallow long density troughs. As a result, the electric
field becomes sawtoothed in nature, with a long region of linearly increasing
field followed by a sharp drop due to the density spikes. In the non-linear
case too, the fluid approximation breaks down for large amplitudes, as
particle sheets cross from neighbouring wave buckets, leading to wavebreaking.
Due to the non-linear steepening, the density spikes have much higher density
than in the linear case, and the value at which wavebreaking occurs (for a
cold relativistic plasma) is given by [12]

$E_{\mathrm{WB}}=\sqrt{2}(\gamma_{\mathrm{ph}}-1)^{1/2}E_{0}.$

The non-linearities in density also causes lengthening of the plasma wave.
This can be seen in aScan2(a), where adding relativistic effects results in an
increasing lengthening of the laser pulse length at which resonance occurs.
This is because the plasma wave wavelength increases as relativistic effects
give the plasma electrons greater inertia. Figure 3(b) shows the increase of
the maximum electric field with increasing laser strength $a_{0}$. At low
intensity, the field increases proportional to $a_{0}{{}^{2}}$, whereas at
high laser strength the dependence becomes closer to $a_{0}$. This dependence
follows the ponderomotive potential of the laser pulse. Because of the non-
linear steepening, the electric field can easily exceed the cold wavebreaking
limit $E_{0}$ at high $a_{0}$. At resonance, the wake amplitude is given by

$E_{\mathrm{max}}\approx\frac{{a_{0}}^{2}}{(1+{a_{0}}^{2})^{1/2}}E_{0}.$

(a) (b)

Figure 3: Wake amplitude for (a) $a_{0}=1$ with varying pulse length for a
linear (blue) and non-linear (red) wake, and (b) $L=\lambda_{\mathrm{p}}$ and
varying $a_{0}$.

##  0.3 Electromagnetic waves

###  0.3.1 The wave equation in vacuum

The wave equation in vacuum is

$\mathbf{\nabla^{2}E}-\frac{1}{c^{2}}\frac{\partial^{2}\textbf{E}}{\partial
t^{2}}=0.$

The _paraxial ray approximation_ assumes that the phase of the electromagnetic
wave varies primarily in $z$, the direction of propagation, i.e.
$\textbf{E}=E(x,y,z)\exp(\mathrm{i}(kz-\omega t))\hat{\textbf{x}}$, which is
true for gentle focussing as in wakefield accelerators. So,

$\nabla^{2}\textbf{E}=\left(\frac{\partial^{2}}{\partial
x^{2}}+\frac{\partial^{2}}{\partial
y^{2}}\right)\textbf{E}+\frac{\partial^{2}E}{\partial
z^{2}}\mathrm{e}^{\mathrm{i}(kz-\omega
t)}\hat{\textbf{x}}+\mathrm{i}k\mathrm{e}^{\mathrm{i}(kz-\omega
t)}\frac{\partial E}{\partial z}\hat{\textbf{x}}-k^{2}\textbf{E}.$

The last term, $k^{2}\textbf{E}$, cancels with
$\displaystyle\frac{1}{c^{2}}\frac{\partial^{2}\textbf{E}}{\partial
t^{2}}=\frac{\omega^{2}}{c^{2}}\textbf{E}$ since $\omega\approx ck$, and we
can assume that the variation in $z$ is slow, so that
$\displaystyle\frac{\partial^{2}E}{\partial z^{2}}\rightarrow 0$, leading to

$\left(\frac{\partial^{2}}{\partial x^{2}}+\frac{\partial^{2}}{\partial
y^{2}}\right)E-2\mathrm{i}k\frac{\partial E}{\partial
z}=0.\tag{cartesianparaxialraywaveequation}$

In two dimensions, e.g., taking $\displaystyle\frac{\partial^{2}E}{\partial
y^{2}}=0$, the equation forms a time-dependent Schrödinger equation.

###  0.3.2 Gaussian optics

For a cylindrically symmetric beam, the paraxial ray equation can be
rewritten:

$\frac{\partial^{2}E}{\partial r^{2}}+\frac{1}{r}\frac{\partial E}{\partial
r}-2\mathrm{i}k\frac{\partial E}{\partial z}=0.\tag{paraxialraywaveequation}$

This equation has a solution of the form:

$E(r,z)=\frac{w_{0}}{w}\exp\left[\frac{-r^{2}}{w^{2}}-\frac{\mathrm{i}\pi
r^{2}}{\lambda R}+\mathrm{i}\phi_{0}\right],$

where

$w=w_{0}\sqrt{1+\left(\frac{z}{z_{\mathrm{R}}}\right)^{2}},\tag{beamwaist}$
$R=\frac{1}{z}\left(z^{2}+{z_{\mathrm{R}}}^{2}\right),\tag{radiusofcurvature}$
$\tan\phi_{0}=\frac{\lambda z}{\pi{w_{0}}^{2}},\tag{Gouyphase}$

where $\displaystyle z_{\mathrm{R}}=\frac{\pi{w_{0}}^{2}}{\lambda}$ is the
Rayleigh length, and $w_{0}$ is the beam waist, and its variation in vacuum
can be seen in the gaussOpt. The beam has a minimum at $z=0$ and like an
unconstrained wave packet, will disperse with increasing propagation. $R$ is
the curvature of the incoming phase fronts and $\phi_{0}$ is known as the Gouy
phase, which flips through zero as a beam passes through focus.

Figure 4: Evolution of beam waist (red line) of an ideal Gaussian beam, with
curvature of phase fronts (blue lines) and Rayleigh range, $z_{\mathrm{R}}$,
(shaded grey) also shown.

The intensity is then given by
$\displaystyle{I}(r,z)/I_{0}=\frac{w_{0}^{2}}{w^{2}}\exp\left[\frac{-2r^{2}}{w^{2}}\right]$,
so for $z=\pm z_{\mathrm{R}}$, the intensity falls by half. As can be seen in
gaussOpt, this is also the distance over which the phase fronts are
approximately flat. For $z\gg z_{\mathrm{R}}$, the beam waist expands almost
linearly with an angle given by

$\tan\theta=\lim_{z\gg
z_{\mathrm{R}}}\left[\frac{w}{z}\right]=\frac{w_{0}}{z_{\mathrm{c}}}=\frac{\lambda}{\pi
w_{0}}.$

Or $\displaystyle\theta\sim\frac{1}{\pi F}$, where the $F$-number,
$\displaystyle F=\frac{w_{0}}{\lambda}=\frac{f}{d}$, which is the ratio of
focal length, $f$, to the beam diameter at the final mirror, $d$.

For wakefield generation, it would seem advantageous to have as high an
intensity as possible, i.e. focusing to small focal spot size. This however
implies a short Rayleigh range and so a short acceleration distance. To try to
maintain a near constant intensity over the interaction distance
($z_{\mathrm{R}}>L_{\mathrm{deph}}$) would require gentle focussing. This has
an implication though for the real size of a plasma accelerator, since the
beam diameter is typically constrained by damage thresholds on the final
turning mirror ($I_{\mathrm{dam}}\sim 10^{12}$ W cm-2), which then has to be
further away from final focus for a longer focal length interaction. Luckily,
plasma effects can help guide an intense laser beam for distances much longer
than the Rayleigh range, alleviating this problem.

###  0.3.3 Propagation in plasma

The wave equation including the effect of plasma can be written

$\mathbf{\nabla^{2}E}-\frac{\eta^{2}}{c^{2}}\frac{\partial^{2}\textbf{E}}{\partial
t^{2}}=0,$

where $\eta$, the plasma refractive index, is given by

$\eta_{\mathrm{R}}\simeq
1-\frac{\omega_{\mathrm{p}}{{}^{2}}}{2\omega^{2}}\frac{n(r)}{n_{0}\gamma_{\perp}},$

for the case of sufficiently underdense plasmas, i.e.
${\omega_{\mathrm{p}}{{}^{2}}}/{\omega^{2}}\ll 1$. Note that both the density
profile $n(r)$ and the relativistic factor $\gamma_{\perp}(r)$ can now vary
radially, in the latter case due to the dependence of $\gamma_{\perp}$ on
intensity, i.e. $\gamma_{\perp}=\sqrt{1+(a_{0}^{2}/2)}$ for linear
polarization.

Either an intensity decrease away from the axis of propagation ($\partial
a^{2}/\partial r^{2})<0$ or a density increase ($\partial
n_{\mathrm{e}}^{2}/\partial r^{2}>0$) can lead to a higher refractive index
on-axis and so, like an optical fibre, causes flow of energy towards the axis
or self-focusing. For small variations, the refractive index can be written

$\eta_{\mathrm{R}}\simeq
1-\frac{\omega_{\mathrm{p}}{{}^{2}}}{2\omega^{2}}\left(1+\frac{\delta
n}{n_{0}}-\frac{a^{2}}{2}\right),$

where $\delta n$ is the density depression, which can be due to a number of
effects such as a preformed channel, or ponderomotive expulsion of plasma
electrons.

(a)  (b)  (c)  (d)  (e)

Figure 5: Behaviour of laser beam waist focussed on boundary of sharp density
plasma transition for $P/P_{\mathrm{cr}}=$ (a) 0, (b) 0.5, (c) 0.9, (d) 1.0
and (e) 1.1.

A Gaussian laser pulse with transverse variation
$a(r)=a_{0}\exp(-r^{2}/R^{2})$, where $R$ is now the beam waist, can be used
as a trial solution to the paraxial ray equation. Keeping only dominant terms,
the evolution of the beam waist can be approximated by [9]

$\frac{\mathrm{d}^{2}R}{\mathrm{d}z^{2}}=\frac{1}{z_{\mathrm{R}}{{}^{2}}R^{3}}\left(1-\frac{P}{P_{\mathrm{c}}}\right).$

The spot size has been normalized to $r_{0}$, the minimum vacuum focal spot
size of the laser pulse and the power unit $P_{\mathrm{c}}\simeq
17({\omega{{}^{2}}}/{{\omega_{\mathrm{p}}}^{2}})$ GW, which is dependent on
density. Figure 5 demonstrates the effect of $P/P_{\mathrm{cr}}$ on the
evolution of the beam waist. Increasing $P/P_{\mathrm{cr}}$ leads to a greater
influence of the second term, which is due to intensity effects, over the
first term which causes diffraction. At $P=P_{\mathrm{cr}}$, a balance is
formed between diffraction and self-focusing and the laser pulse can be
guided. Hence this is a _critical_ power for self-focusing. For
$P>P_{\mathrm{cr}}$, the model predicts catastrophic self-focusing. In reality
however, including higher order diffraction terms prevents this as strong
focussing invariably leads to generation of higher modes and thus
filamentation [13].

###  0.3.4 Guiding

For wakefield driving short pulses, the leading edge of the pulse interacts
with the wrong curvature of density due to the plasma wave (increasing on-
axis) and this can cause increased diffraction of the laser pulse. This is
true even if the body of the laser pulse is being self-focused. To overcome
this, guiding channels are used, where the guiding of the pulse is now
determined by

$\frac{\mathrm{d}^{2}R}{\mathrm{d}z^{2}}=\frac{1}{z_{\mathrm{R}}{{}^{2}}R^{3}}\left(1-\frac{\delta
n}{\delta n_{\mathrm{c}}}R^{4}\right).$

A Gaussian beam with $R=1$, i.e. $r=r_{0}$, can be guided, provided there is a
density depression with $\delta n=\delta n_{\mathrm{c}}$, where

$\delta n_{\mathrm{c}}=\frac{1}{\pi r_{\mathrm{e}}r_{0}{{}^{2}}},$ (5)

and $r_{\mathrm{e}}=e^{2}/m_{\mathrm{e}}{{}^{2}}c^{2}$ is the ‘classical
radius of the electron’. Such channels can be formed, for example, by thermal
equilibration of a discharge with its cold walls, or by ponderomotive or
thermal expulsion of a plasma by a secondary laser pulse [14]. Channel guiding
allows laser energy to be used more efficiently in a laser wakefield and also
allows potentially simpler operation in the linear regime.

(a)  (b)  (c)  (d)  (e)

Figure 6: Behaviour of the waist of the leading edge of a laser pulse focussed
on boundary of sharp density transition on a plasma with radial guiding
channel with $\delta n/\delta n_{\mathrm{cr}}=$ (a) 0, (b) 0.1, (c) 0.5, (d)
1.0 and (e) 1.4.

There is a critical beam or ‘matched’ spot size at which the beam propagates
with minimum channel waist oscillations (see channelFoc), as can be found by
inverting eqn:matched. The goal for laser wakefield operation is to match the
Gaussian focussed laser spot to the matched spot of the accelerator, which
determines the required focussing parameter. However, as can be seen in the
figure, not focussing at the matched spot size will lead to channel
oscillations which can lead to a loss of guided energy, as the channels are
invariably ‘leaky’.

###  0.3.5 Propagation effects

A laser pulse of course does not stay unchanged as it drives a wakefield, it
must lose energy. However this does not necessarily lead to a reduction in
intensity, since the pulse can compress as it propagates. In a linear wake,
the rate of compression is given by the difference in the group velocity from
the first maximum to minimum of the plasma wave. This can be seen in compress
which shows that due to the density rise, the front of the laser pulse has a
slower group velocity than the rear of the pulse, causing the back to ‘catch-
up’ and the pulse to compress. For the case of a pulse with
$L\sim\lambda_{\mathrm{p}}$, the variation of pulse length as a function of
propagation distance $\ell$ is [15]

$\tau=\tau_{0}-\frac{n_{e0}l}{2n_{\mathrm{cr}}c}.$

The pulse compression has the beneficial effect that the power of the driving
pulse can stay relatively constant, even though the energy within the laser
pulse is being progressively reduced. The laser pulse also redshifts from the
front as those photons that drive the wakefield lose energy. This almost
complete loss of energy of the driving photons leads to an etching of the
laser pulse. By contrast the trailing photons in the wake are ‘squeezed’ as
they travel in the density depression and so become blue shifted. This process
is often called photon acceleration and the amount of blue shifting (energy
gain) of the photon is given by [16]

$\delta\omega=\omega_{0}\left(1-z\frac{\mathrm{d}\beta_{\mathrm{p}}}{\mathrm{d}\zeta}\right)\simeq\omega_{0}\left(1-z\frac{\mathrm{d}}{\mathrm{d}\zeta}\left(\frac{\delta
n}{n_{0}}\right)\right).$

Photon acceleration can be a useful diagnostic of wakefields in cases where
there are no charged particles available to accelerate [17].

(a) (b)

Figure 7: Compression and photon acceleration of a wakefield driving laser
pulse for $a_{0}=1$, $L=\lambda_{\mathrm{p}}$. (a) $n_{\mathrm{e}}$ (top),
_group_ velocity (middle) and pulse shape (bottom) showing regions of speeding
and slowing of the pulse. (b) $n_{\mathrm{e}}$ (top), _phase_ velocity
(middle) and pulse shape (bottom) showing regions of stretching and
compressing of phase.

##  0.4 Conclusion

We have discussed a number of effects which are important for laser wakefield
acceleration. We have shown how non-linear effects increase the plasma wave
wavelength and also allow larger wakefield amplitudes at high intensities
($a_{0}>1$). This is due to the characteristic peak and trough nature of the
non-linear wakes in this regime.

We have also discussed simple models for the guiding of laser pulses which
allow the length of a laser wakefield well beyond the Rayleigh range of the
laser pulse. This is important as it allows the full energy gain to be
extracted from the laser wakefield. We also discussed how preformed channels
can enhance the guiding effect for a laser pulse focussed to the matched spot
size of the channel.

## References

  * [1] T. Tajima and J. M. Dawson, Phys. Rev. Lett. 43 (1979) 267. http://dx.doi.org/10.1103/PhysRevLett.43.267.
  * [2] S. Kneip _et al._ , Phys. Rev. Lett. 103 (2009) 035002. http://dx.doi.org/10.1103/PhysRevLett.103.035002
  * [3] X. Wang _et al._ , Nature Commun. 4 (2013) 1988. http://dx.doi.org/10.1038/ncomms2988
  * [4] H.T. Kim, K.H. Pae, H.J. Cha, I.J. Kim, T.J. Yu, J.H. Sung, S.K. Lee, T.M. Jeong and J. Lee, Phys. Rev. Lett. 111 (2013) 165002. http://dx.doi.org/10.1103/PhysRevLett.111.165002
  * [5] W.P. Leemans _et al._ , Phys. Rev. Lett. 113 (2014) 245002. http://dx.doi.org/10.1103/PhysRevLett.113.245002
  * [6] P. Chen, J.M. Dawson, R.W. Huff and T. Katsouleas, Phys. Rev. Lett. 54 (1985) 693. http://dx.doi.org/10.1103/PhysRevLett.54.693
  * [7] B.E. Blue _et al._ , _Phys. Rev. Lett._ 90 (2003) 214801. http://dx.doi.org/10.1103/PhysRevLett.90.214801
  * [8] A. Caldwell, K. Lotov, A. Pukhov and F. Simon, Nature Phys. 5 (2009) 363–367. http://dx.doi.org/10.1038/nphys1248
  * [9] E. Esarey, P. Sprangle, J. Krall and A. Ting, IEEE Trans. Plasma Sci. 24 (1996) 252–288. http://dx.doi.org/10.1109/27.509991
  * [10] J.M. Dawson, Phys. Rev. 113 (1959) 383. http://dx.doi.org/10.1103/PhysRev.113.383
  * [11] A. Modena _et al._ , Nature 377 (1995) 606. http://dx.doi.org/10.1038/377606a0
  * [12] A.I. Akhiezer and R.V. Polovin, Sov. Phys. JETP 3(5) (1956) 696.
  * [13] A.G.R. Thomas _et al._ , Phys. Rev. Lett. 98 (2007) 2. http://dx.doi.org/10.1103/PhysRevLett.98.054802
  * [14] E. Esarey, P. Sprangle, J. Krall, and A. Ting, IEEE J. Quantum Electron. 33, (1997) 1879. http://dx.doi.org/10.1109/3.641305
  * [15] J. Schreiber _et al._ , Phys. Rev. Lett. 105 (2010) 235003. http://dx.doi.org/10.1103/PhysRevLett.105.235003
  * [16] S.C. Wilks, J.M. Dawson, W.B. Mori, T. Katsouleas and M.E. Jones, Phys. Rev. Lett. 62 (1989) 2600. http://dx.doi.org/10.1103/PhysRevLett.62.2600
  * [17] C.D. Murphy _et al._ , Phys. Plasmas 13 (2006) 033108. http://dx.doi.org/10.1063/1.2178650

## Bibliography

P. Gibbon, _Short Pulse Laser Interactions with Matter_ (World Scientific
Publishing Company, New York, 2004).