chains,fit shapes,arrows shapes.geometric matrix,positioning,calc
decorations.markings decorations.pathmorphing decorations.pathreplacing
vertex=[circle, draw, inner sep=0pt, minimum size=6pt] vertbox=[draw, inner
sep=0pt, minimum size=8pt]

# Finding Geometric Representations of Apex Graphs is NP-Hard

Dibyayan Chakraborty and Kshitij Gajjar Indian Institute of Science,
Bengaluru. E-mail<EMAIL_ADDRESS>University of Singapore,
Singapore. A part of this work was done when the author was a postdoctoral
researcher at Technion, Israel. E-mail<EMAIL_ADDRESS>
###### Abstract

Planar graphs can be represented as intersection graphs of different types of
geometric objects in the plane, e.g., circles (Koebe, 1936), line segments
(Chalopin & Gonçalves, 2009), L-shapes (Gonçalves et al., 2018). For general
graphs, however, even deciding whether such representations exist is often
$\NP$-hard. We consider apex graphs, i.e., graphs that can be made planar by
removing one vertex from them. We show, somewhat surprisingly, that deciding
whether geometric representations exist for apex graphs is $\NP$-hard.

More precisely, we show that for every positive integer $k$, recognizing every
graph class $\mathcal{G}$ which satisfies
$\textup{{Pure-2-Dir}}\subseteq\mathcal{G}\subseteq\textup{{1-String}}$ is
$\NP$-hard, even when the input graphs are apex graphs of girth at least $k$.
Here, Pure-2-Dir is the class of intersection graphs of axis-parallel line
segments (where intersections are allowed only between horizontal and vertical
segments) and 1-String is the class of intersection graphs of simple curves
(where two curves share at most one point) in the plane. This partially
answers an open question raised by Kratochvíl & Pergel (2007).

Most known $\NP$-hardness reductions for these problems are from variants of
3-SAT. We reduce from the Planar Hamiltonian Path Completion problem, which
uses the more intuitive notion of planarity. As a result, our proof is much
simpler and encapsulates several classes of geometric graphs.

Keywords: Planar graphs, apex graphs, NP-hard, Hamiltonian path completion,
recognition problems, geometric intersection graphs, 1-STRING, PURE-2-DIR.

##  1 Introduction

The recognition a graph class is the decision problem of determining whether a
given simple, undirected, unweighted graph belongs to the graph class.
Recognition of graph classes is a fundamental research topic in discrete
mathematics with applications in VLSI design [CLR83, CLR84, She07]. In
particular, when the graph class relates to intersection patterns of geometric
objects, the corresponding recognition problem finds usage in disparate areas
like map labelling [AVK98], wireless networks [KWZ08], and computational
biology [XB06]. The applicability of the recognition problem further increases
if the given graph is planar.

Several $\NP$-hard graph problems admit efficient algorithms for planar graphs
[Sto73, HW74, Had75]. There are many reasons behind this, owing to the nice
structural properties of planar graphs [Tut63, LT79]. Since most of the graphs
are non-planar (i.e., the fraction of $n$-vertex graphs that are planar
approaches zero as $n$ tends to infinity), it is worthwhile to explore whether
these efficient algorithms continue to hold for graphs that are “close to”
planar. Specifically, we deal with apex graphs.

######  Definition 1.

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

Since every $n$-vertex apex graph contains an $(n-1)$-vertex planar graph as
an induced subgraph, one might expect apex graphs to retain some of the
properties of planar graphs, in the hope that efficient algorithms for planar
graphs carry forward to apex graphs as well. In this paper, we show that for
recognition problems for several classes of geometric intersection graphs,
this is not the case.

The intersection graph of a collection $C$ of sets is a graph with vertex set
$C$ in which two vertices are adjacent if and only if their corresponding sets
have a non-empty intersection. For our main result, we are particularly
interested in two natural and well-studied classes of geometric intersection
graphs (i.e., when the sets in the collection $C$ are geometric objects in the
plane) called Pure-2-Dir and 1-String, shown111This illustration is only for
representational purposes. in Figure 1.

######  Definition 2.

Pure-2-Dir is the class of all graphs $G$, such that $G$ is the intersection
graph of axis-parallel line segments in the plane, where intersections are
allowed only between horizontal and vertical segments.

######  Definition 3.

1-String is the class of all graphs $G$, such that $G$ is the intersection
graph of simple curves222Formally, a simple curve is a subset of the plane
which is homeomorphic to the interval $[0,1]$. in the plane, where two
intersecting curves share exactly one point, at which they must cross each
other.

######  Theorem 4 (Main Result).

Let $g$ be a positive integer and $\mathcal{G}$ be a graph class such that
$\textup{{Pure-2-Dir}}\subseteq\mathcal{G}\subseteq\textup{{1-String}}.$ Then
it is $\NP$-hard to decide whether an input graph belongs to $\mathcal{G}$,
even when the input graphs are restricted to bipartite apex graphs of girth at
least $g$.

Pure-2-Dir$\mathcal{G}$1-String

Figure 1: A visual depiction of our main result (4).

In Figure 1, note that in the Pure-2-Dir (2) representation, two vertical
(similarly, two horizontal) line segments do not intersect each other. Also
note that in the 1-String (3) representation, two intersecting curves share
exactly one point, and the curves do not touch (tangentially) but instead
cross each other at that point. Our main result states that the recognition of
every graph class $\mathcal{G}$ that lies between these two is $\NP$-hard,
even if the input graph is bipartite, apex, and has large girth. Some
candidate graph classes for $\mathcal{G}$ are shown in Subsection 1.1.

Paper Roadmap: In Subsection 1.1, we highlight some implications of our main
result and in Subsection 1.2, we survey the existing literature on the topic.
In Section 2, we describe our proof techniques and give an overview of our
proof. In Section 3, we prove 4 and draw some conclusions in Section 5.

###  1.1 Significance of the Main Result

Our main result has several corollaries, obtained by substituting different
values for the graph class $\mathcal{G}$. Recall that the recognition of a
graph class $\mathcal{G}$ asks if a given graph $G$ is a member of
$\mathcal{G}$.

String is the class of intersection graphs of simple curves in the plane.
Kratochvíl & Pergel [KP07] posed the question of determining the complexity of
recognizing String when the inputs are restricted to graphs with large girth.
The above question was answered by Mustaţă & Pergel [MP19], where they showed
that recognizing String is $\NP$-hard, even when the inputs are restricted to
graphs of arbitrarily large girth. However, the graphs they constructed were
far from planar. Since $\textup{{1-String}}\subsetneq\textup{{String}}$, the
following corollary of our main result partially answers Kratochvíl & Pergel’s
[KP07] question when the inputs are restricted to apex graphs of large girth.

######  Corollary 5.

For every positive integer $g$, recognizing 1-String is $\NP$-hard, even for
bipartite apex graphs with girth at least $g$.

Chalopin & Gonçalves [CG09] showed that every planar graph can be represented
as an intersection graph of line segments in polynomial time. The following
corollary shows that a similar result does not hold for apex graphs.

######  Corollary 6.

For every positive integer $g$, recognizing intersection graphs of line
segments is $\NP$-hard, even for bipartite apex graphs with girth at least
$g$.

Gonçalves, Isenmann & Pennarun [GIP18] showed that every planar graph can be
represented as an intersection graph of L-shapes in polynomial time. The
following corollary shows that a similar result does not hold for apex graphs.

######  Corollary 7.

For every positive integer $g$, recognizing intersection graphs of L-shapes is
$\NP$-hard, even for bipartite apex graphs with girth at least $g$.

Our main result also has a connection to a graph invariant called  _boxicity_.
The boxicity of a graph is the minimum integer $d$ such that the graph can be
represented as an intersection graph of $d$-dimensional axis-parallel boxes.
Thomassen showed three decades ago that the boxicity of every planar graph is
either one, two or three [Tho86]. It is easy to check if the boxicity of a
planar graph is one [BL76]. However, the complexity of determining whether a
planar graph has boxicity two or three is not yet known. A result of Hartman,
Newman & Ziv [HNZ91] states that the class of bipartite graphs with boxicity 2
is precisely Pure-2-Dir. Combined with our main result, this implies that
determining the boxicity of apex graphs is $\NP$-hard.

######  Corollary 8.

For every positive integer $g$, recognizing graphs with boxicity $2$ is
$\NP$-hard, even for bipartite apex graphs with girth at least $g$.

Conv is the class of intersection graphs of convex objects in the plane.
Kratochvíl & Pergel [KP07] asked if recognizing Conv remains $\NP$-hard when
the inputs are restricted to graphs with large girth. Note that the class of
graphs with boxicity $2$ (alternatively, intersection graphs of rectangles) is
a subclass of Conv. Similarly, intersection graphs of line segments on the
plane is also a subclass of Conv. Hence, 6 and 8 also partially address the
aforementioned open question of Kratochvíl & Pergel [KP07].

A graph is $c$-apex if it contains a set of $c$ vertices whose removal makes
it planar. This is a natural generalization of apex graphs. Our main result
implies that no graph class $\mathcal{G}$ satisfying
$\textup{{Pure-2-Dir}}\subseteq\mathcal{G}\subseteq\textup{{1-String}}$ can be
recognized in $n^{f(c)}$ time, where $f$ is a computable function depending
only on $c$. This means recognizing $\mathcal{G}$ is $\XP$-hard, and thus not
fixed-parameter tractable [Nie06, DF12] for $c$-apex graphs when parameterized
by $c$.

######  Corollary 9.

Let $g$ be a positive integer and $\mathcal{G}$ be a graph class such that

$\textup{{Pure-2-Dir}}\subseteq\mathcal{G}\subseteq\textup{{1-String}}.$

Then assuming $\P\neq\NP$, there is no $f(c)\cdot n^{O(1)}$ time algorithm
that recognizes $\mathcal{G}$ (where $f$ is a computable function depending
only on $c$), even for bipartite $c$-apex graphs with girth at least $g$.

Thanks to a long line of work due to Robertson & Seymour [RS04], several graph
classes can be characterized by a finite set of forbidden minors. For example,
planar graphs are $(K_{5},K_{3,3})$-minor free graphs. Interestingly, the set
of forbidden minors is not known for apex graphs, although it is known that
the set is finite [GI91]. However, it is easy to see that apex graphs are
$K_{6}$-minor free, which means that our main result has the following
implication.

######  Corollary 10.

Let $g$ be a positive integer and $\mathcal{G}$ be a graph class such that

$\textup{{Pure-2-Dir}}\subseteq\mathcal{G}\subseteq\textup{{1-String}}.$

Then it is $\NP$-hard to decide whether an input graph belongs to
$\mathcal{G}$, even for bipartite $K_{6}$-minor free graphs with girth at
least $g$.

Finally, using techniques different from ours, Kratochvíl & Matoušek [KM89]
had shown that recognizing Pure-2-Dir is $\NP$-hard, and so is the recognition
of line segment intersection graphs. 4 and 6 show that these recognition
problems remain $\NP$-hard even when the inputs are restricted to bipartite
apex graphs of arbitrarily large girth, thereby strengthening their results.

###  1.2 Related Work

In this paper, we focus on recognition problems for subclasses of string
graphs. A graph is called a string graph if it is the intersection graph of a
set of simple curves in the plane. Benzer [Ben59] initiated the study of
string graphs over half a century ago. Sinden, in his seminal paper [Sin66],
asked whether the recognition of string graphs is decidable. Kratochvíl
[Kra91] took the first steps towards answering Sinden’s question by showing
that recognizing string graphs is $\NP$-hard. Schaefer, Sedgwick &
Štefankovič, [SSŠ03] settled Sinden’s question by showing that the recognition
of string graphs also lies in $\NP$, and is thus $\NP$-complete.

Finding representations of planar graphs using geometric objects has been a
very popular and exciting line of research. The celebrated Circle Packing
Theorem [Koe36] (also see [And70, Thu82]) states that all planar graphs can be
expressed as intersection graphs of touching disks. This result also implies
that planar graphs are string graphs. In his PhD thesis, Scheinerman [Sch84]
conjectured that planar graphs can be expressed as intersection graphs of line
segments. Scheinerman’s conjecture was first shown to be true for bipartite
planar graphs [HNZ91], and later extended to triangle-free planar graphs
[DCCD+99]. Chalopin, Gonçalves & Ochem [CGO10] proved a relaxed version of
Scheinerman’s conjecture by showing that every planar graph is in 1-String.
Scheinerman’s conjecture was finally proved in 2009 by Chalopin & Gonçalves
[CG09]. More recently, Gonçalves, Isenmann & Pennarun [GIP18] showed that
planar graphs are intersection graphs of L-shapes. Soon thereafter, Gonçalves,
Lévêque & Pinlou [GLP19] showed that planar graphs are also intersection
graphs of homothetic triangles.

Another interesting subclass of string graphs is $k$-Dir [CJ17]. A graph $G$
is in $k$-Dir (and has a $k$-Dir representation) if $G$ is the intersection
graph of line segments whose slopes belong to a set of at most $k$ real
numbers. Moreover, $G$ is in Pure-$k$-Dir if $G$ has a $k$-Dir representation
where no two segments of the same slope intersect. West [Wes91] conjectured
that every planar graph is in Pure-$4$-Dir. A proof of West’s conjecture would
have provided an alternate proof for the famous Four Color Theorem [AH77] for
planar graphs. Indeed, every bipartite planar graph is in Pure-2-Dir and every
$3$-colourable planar graph is in Pure-$3$-Dir [HNZ91, Gon19]. However,
Gonçalves [Gon20] proved in 2020 that West’s conjecture is false.

Motivated by the long history of research on geometric intersection
representations of planar graphs, we show in this paper that finding geometric
intersection representations of apex graphs is $\NP$-hard. Our proof technique
(Section 2) deviates considerably from earlier $\NP$-hardness proofs for
recognition of geometric intersection graphs, all of which were based on
different variants of 3-SAT. We elaborate on this below.

In a highly influential paper, Kratochvíl [Kra94] introduced a variant of
3-SAT called 4-Bounded Planar 3-Connected 3-SAT (4P3C3SAT), and showed that it
is $\NP$-hard. He then used 4P3C3SAT to show that recognizing Pure-2-Dir is
$\NP$-hard. Chmel [Chm20] reduced the 4P3C3SAT problem to show that
recognizing intersection graphs of L-shapes is $\NP$-hard. Kratochvíl & Pergel
[KP07] used 4P3C3SAT to show that recognizing intersection graphs of line
segments is $\NP$-hard even if the inputs are restricted to graphs with large
girth. Mustaţă & Pergel [MP19] also used 4P3C3SAT to generalize and strengthen
the above result by showing that there is no polynomial time recognizable
graph class that lies between Pure-2-Dir and String, even when the inputs are
restricted to graphs with arbitrarily large girth and maximum degree at most
$8$. Chaplick, Jelínek, Kratochvíl & Vyskočil [CJKV12] used similar techniques
to show that the recognition of intersection graphs of rectilinear curves
having at most $k$ bends (for every constant $k$) is $\NP$-hard.

The construction of the variable and clause gadgets used in these reductions
is sometimes quite involved, which ends up making the proofs rather
complicated. Perhaps the reason behind this is that even though the incidence
graph (of clauses and variables) of a 4P3C3SAT instance is planar, the
variable and clause gadgets are non-planar, producing graphs that are far from
planar. We overcome this difficulty by reducing from the $\NP$-hard Planar
Hamiltonian Path Completion problem [AG11], which in turn was inspired by the
$\NP$-hard Planar Hamiltonian Cycle Completion problem [Wig82]. Reducing from
this problem allows us to use the natural notion of planarity, making our
proofs easier to follow. We explain this in the next section (Section 2).

$v_{1}$ $v_{2}$ $v_{3}$ $v_{4}$ $v_{5}$ $v_{6}$ $v_{7}$ $v_{8}$ |  $v_{1}$ $v_{2}$ $v_{3}$ $v_{4}$ $v_{5}$ $v_{6}$ $v_{7}$ $v_{8}$ |  $v_{1}$ $v_{2}$ $v_{3}$ $v_{4}$ $v_{5}$ $v_{6}$ $v_{7}$ $v_{8}$ $a$
---|---|---
(a) | (b) | (c)
| $\mathtt{c}(v_{8})$$\mathtt{c}(v_{7})$$\mathtt{c}(v_{6})$$\mathtt{c}(v_{5})$$\mathtt{c}(v_{4})$$\mathtt{c}(v_{3})$$\mathtt{c}(v_{2})$$\mathtt{c}(v_{1})$$\mathtt{c}(a)$ |
| (d) |

Figure 2: (a) A front line drawing (12) of a planar graph $G$, where $G$ is a
yes-instance of Planar Hamiltonian Path Completion (11), and the vertical
dotted line denotes the front line $\ell_{\mathsf{front}}$; (b)
$G_{k\operatorname{-{\mathsf{div}}}}$ for $k=3$; (c) $G_{\mathsf{apex}}$; (d)
$C$, a Pure-2-Dir representation of $G_{\mathsf{apex}}$ (Subsection 3.3).

##  2 Proof Techniques

Let us now describe the Planar Hamiltonian Path Completion problem [AG11]. A
Hamiltonian path in a graph is a path that visits each vertex of the graph
exactly once.

######  Definition 11.

Planar Hamiltonian Path Completion is the following decision problem.

Input: A planar graph $G$.

Output: Yes, if $G$ is a subgraph of a planar graph with a Hamiltonian path;
no, otherwise.

Auer & Gleißner [AG11] showed that this problem (11) is $\NP$-hard. For their
proof, they defined the following constrained planar embedding (Figure 2 (a)).

######  Definition 12 (Front line drawing).

A front line drawing of a planar graph $G$ is a planar embedding of $G$ such
that its vertices lie on a vertical line segment $\ell_{\mathsf{front}}$
(called the  _front line_ by Auer & Gleißner [AG11]) and its edges do not
cross each other or $\ell_{\mathsf{front}}$. Let $e=v_{i}v_{j}$ be an edge of
$G$ such that $e$ connects to the vertex $v_{i}$ from the left of
$\ell_{\mathsf{front}}$, and to the vertex $v_{j}$ from the right of
$\ell_{\mathsf{front}}$. We call such an edge a  _crossover edge_. Figure 2
(a) is a front line drawing with two crossover edges, namely $v_{5}v_{7}$ and
$v_{4}v_{2}$.

######  Observation 13 (Auer & Gleißner [AG11]).

A planar graph $G$ is a yes-instance of the Planar Hamiltonian Path Completion
problem if and only if $G$ admits a front line drawing.

Using this observation, they showed that deciding whether a graph $G$ admits a
front line drawing is $\NP$-hard, implying the required theorem.

######  Theorem 14 (Auer & Gleißner [AG11]).

Planar Hamiltonian Path Completion is $\NP$-hard.

We will use 14 to show our main result (4). We show $\NP$-hardness for graph
classes “sandwiched” between two classes of geometric intersection graphs,
similar to Mustaţă & Pergel [MP19]. A more technical formulation of our main
result is as follows.

######  Theorem 15.

For every planar graph $G$ and positive integer $g$, there exists a bipartite
apex graph $G_{\mathsf{apex}}$ of girth at least $g$ which can be obtained in
polynomial time from $G$, satisfying the following properties.

  1. (a)

If $G_{\mathsf{apex}}$ is in 1-String, then $G$ is a yes-instance of Planar
Hamiltonian Path Completion.

  2. (b)

If $G$ is a yes-instance of Planar Hamiltonian Path Completion, then
$G_{\mathsf{apex}}$ is in Pure-2-Dir.

###### Proof of 4 assuming 15.

Let $\mathcal{G}$ be a graph class satisfying the condition
$\textup{{Pure-2-Dir}}\subseteq\mathcal{G}\subseteq\textup{{1-String}}$, and
let $G$ be a planar graph. If $G$ is a yes-instance of Planar Hamiltonian Path
Completion, then by 15 (b),
$G_{\mathsf{apex}}\in\textup{{Pure-2-Dir}}\subseteq\mathcal{G}$. And if
$G_{\mathsf{apex}}\in\mathcal{G}\subseteq\textup{{1-String}}$, then by 15 (a),
$G$ is a yes-instance of Planar Hamiltonian Path Completion.

Thus, $G_{\mathsf{apex}}\in\mathcal{G}$ if and only if $G$ is a yes-instance
of Planar Hamiltonian Path Completion. Since Planar Hamiltonian Path
Completion is $\NP$-hard (14) and $G_{\mathsf{apex}}$ can be obtained in
polynomial time from $G$, this implies that deciding whether the bipartite
apex graph $G_{\mathsf{apex}}$ belongs to $\mathcal{G}$ is $\NP$-hard. ∎

Therefore, as 15 implies our main result (4), the rest of this paper is
devoted to the proof of 15.

##  3 Proof of the Main Result

$v_{5}$$v_{2}$$v_{4}$$v_{1}$$v_{3}$$v_{5}$$v_{2}$$v_{4}$$v_{1}$$v_{3}$

Figure 3: (Left) A standard representation of a planar graph, where the
vertices are points and the edges are strings. (Right) A planarizable
representation (17) of the same graph, where the vertices as well as the edges
are strings.

###  3.1 Construction of the Apex Graph

We begin our proof of 15 by describing the construction of
$G_{\mathsf{apex}}$. Let $G$ be a planar graph. $G_{\mathsf{apex}}$ is
constructed in two steps.

$G\rightarrow G_{k\operatorname{-{\mathsf{div}}}}\rightarrow
G_{\mathsf{apex}}.$

Let $g\geq 6$ be a positive integer, and $k\geq 3$ be the minimum odd integer
greater or equal to $g-3$. Let $G_{k\operatorname{-{\mathsf{div}}}}$ be the
full $k$-subdivision of $G$, i.e., $G_{k\operatorname{-{\mathsf{div}}}}$ is
the graph obtained by replacing each edge of $G$ by a path with $k+1$ edges.
Figure 2 (a) denotes a graph $G$, and Figure 2 (b) denotes the full
$3$-subdivision of $G$. Formally, we replace each $e=(x,y)\in E(G)$ by the
path $(x,u^{1}_{e},u^{2}_{e},u^{3}_{e},\ldots,u^{k}_{e},y)$.

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

We call the vertices of $V(G)\subseteq V(G_{k\operatorname{-{\mathsf{div}}}})$
as the  _original vertices_ of $G_{k\operatorname{-{\mathsf{div}}}}$ and the
remaining vertices as the  _subdivision vertices_ of
$G_{k\operatorname{-{\mathsf{div}}}}$. Finally, we construct
$G_{\mathsf{apex}}$ by adding a new vertex $a$ to
$G_{k\operatorname{-{\mathsf{div}}}}$ and making it adjacent to all the
original vertices of $G_{k\operatorname{-{\mathsf{div}}}}$ (Figure 2 (c)).
Formally, $G_{\mathsf{apex}}$ is defined as follows.

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

######  Observation 16.

If $G$ is a planar graph, then $G_{\mathsf{apex}}$ is a bipartite apex graph
of girth at least $g$.

###### Proof.

$G$ is a planar graph and subdivision does not affect planarity, so
$G_{k\operatorname{-{\mathsf{div}}}}$ is also planar, implying that
$G_{\mathsf{apex}}$ is an apex graph. The vertex set of $G_{\mathsf{apex}}$
can be expressed as the disjoint union of two sets $A$ and $B$, where

$\displaystyle A$ $\displaystyle=\\{x\mid x\in V(G)\\}\cup\\{u^{i}_{e}\mid
e\in E(G),i\text{ is even}\\};$ $\displaystyle B$
$\displaystyle=\\{a\\}\cup\\{u^{i}_{e}\mid e\in E(G),i\text{ is odd}\\}.$

Note that $A$ induces an independent set in $G_{\mathsf{apex}}$, and so does
$B$. Thus, $G_{\mathsf{apex}}$ is a bipartite apex graph. As for the girth,
note that every cycle in $G_{\mathsf{apex}}$ contains at least $k+2$ vertices
$x,u^{1}_{e},u^{2}_{e},u^{3}_{e},\ldots,u^{k}_{e},y$, for some $e=(x,y)\in
E(G)$. At least one more vertex is needed to complete the cycle, implying that
the girth of $G_{\mathsf{apex}}$ is at least $k+3\geq g$. ∎

It is easy to see that this entire construction of $G_{\mathsf{apex}}$ from
$G$ can be carried out in polynomial time. In Subsection 3.2 and Subsection
3.3, we will prove 15 (a) and 15 (b), respectively.

###  3.2 Proof of Theorem 15 (a)

In this section, we will show that if $G_{\mathsf{apex}}$ is in 1-String, then
$G$ is a yes-instance of Planar Hamiltonian Path Completion. In other words,
if $G_{\mathsf{apex}}$ has a 1-String representation, then $G$ is a subgraph
of a planar graph with a Hamiltonian path.

In our proofs, we will demonstrate the planarity of our graphs by embedding
them in the plane. Typically, a planar graph is defined as a graph whose
vertices are  _points_ in the plane and edges are  _strings_ connecting pairs
of points such that no two strings intersect (except possibly at their end
points). The same definition holds in more generality, i.e., if the vertices
are also allowed to be strings (Figure 3). Let us state this formally.

######  Definition 17 (Planarizable representation of a graph).

A graph $G$ on $n$ vertices and $m$ edges is said to admit a planarizable
representation if there are two mutually disjoint sets of strings $V$ and $E\
($with $|V|=n$ and $|E|=m)$ in the plane such that

  * •

the strings of $V$ correspond to the vertices of $G$ and the strings of $E$
correspond to the edges of $G$;

  * •

no two strings of $V$ intersect;

  * •

no two strings of $E$ intersect, except possibly at their end points;

  * •

apart from its two end points, a string of $E$ does not intersect any string
of $V$;

  * •

for every vertex $v$ and every edge $e=(x,y)$ of $G$, an end point of the
string corresponding to $e$ intersects the string corresponding to $v$ if and
only if $v=x$ or $v=y$.

Figure 3 illustrates a planar graph and a planarizable representation of it.

######  Lemma 18.

A graph admits a planarizable representation if and only if it is planar.

18 may seem obvious. For completeness, we provide a formal proof of it in
Section 4. We now use this lemma to prove 15 (a).

###### Proof of 15 (a).

Given $G_{\mathsf{apex}}\in\textup{{1-String}}$, we will show that the planar
graph $G$ is a yes-instance of Planar Hamiltonian Path Completion. Let $C$ be
a 1-String representation of $G_{\mathsf{apex}}$ in the plane. It is helpful
to follow Figure 4 while reading this proof. We will use $C$ to construct a
graph $G_{\mathsf{pl}}$ with the following properties.

  1. (a)

$G_{\mathsf{pl}}$ is a supergraph of $G$ on the same vertex set as $G$.

  2. (b)

$G_{\mathsf{pl}}$ is planar.

  3. (c)

$G_{\mathsf{pl}}$ has a Hamiltonian path.

Note that (a), (b), (c) together imply that $G$ is a subgraph of a planar
graph with a Hamiltonian path (i.e., $G$ is a yes-instance of Planar
Hamiltonian Path Completion). Let $n=|V(G)|$ and assume that $n\geq 4$. Along
with our construction of $G_{\mathsf{pl}}$, we will also describe
$\textsc{Draw}(G_{\mathsf{pl}})$, a planarizable representation (17) of
$G_{\mathsf{pl}}$ in the plane.

In $C$, consider the strings corresponding to the $n$ original vertices (the
ones in blue in Figure 4) of $G$. Since the original vertices form an
independent set in $G_{\mathsf{apex}}$, the blue strings are pairwise
disjoint. We add these $n$ strings to $\textsc{Draw}(G_{\mathsf{pl}})$, which
correspond to the $n$ vertices of $G_{\mathsf{pl}}$.

$v_{5}$$v_{2}$$v_{4}$$v_{1}$$v_{3}$$\mathtt{c}(a)$$\mathtt{c}(v_{4})$$\mathtt{c}(v_{5})$$\mathtt{c}(v_{1})$$\mathtt{c}(v_{2})$$\mathtt{c}(v_{3})$$p_{1}$$p_{2}$
$p_{3}$$p_{4}$$p_{5}$

Figure 4: (Left) $G_{k\operatorname{-{\mathsf{div}}}}$ ($k=3$) for a planar
graph $G$. (Right) $C$, a planarizable representation of $G_{\mathsf{apex}}$.
The bold red string $\mathtt{c}(a)$ denotes the apex vertex of
$G_{\mathsf{apex}}$. The blue strings denote the original vertices of $G$, and
the thin red strings are $\mathtt{c}(u^{1}_{e})$, $\mathtt{c}(u^{2}_{e})$ and
$\mathtt{c}(u^{3}_{e})$, corresponding to the subdivision vertices of $G$.

Proof of (c): So far, $G_{\mathsf{pl}}$ has no edge. We will now add $n-1$
edges to $G_{\mathsf{pl}}$ to connect these vertices via a Hamiltonian path.
Recall that each of the $n$ original vertices is adjacent to the apex vertex
$a$ in $G_{\mathsf{apex}}$, which means that each of the $n$ blue strings
intersects $\mathtt{c}(a)$ at precisely one point (since $C$ is a 1-String
representation). Starting from one end point of $\mathtt{c}(a)$ and travelling
along the curve $\mathtt{c}(a)$ until we reach its other end point, we
encounter these $n$ points one-by-one. Let $(v_{1},v_{2},\ldots,v_{n})$ be the
order in which they are encountered.

For each $i\in[n]$, let $p_{i}$ be the point at which $\mathtt{c}(v_{i})$
intersects $\mathtt{c}(a)$. For each $i\in[n-1]$, let $\mathtt{s_{i}}$ be the
substring of $\mathtt{c}(a)$ between $p_{i}$ and $p_{i+1}$. Add the strings
$\mathtt{s_{1}},\mathtt{s_{2}},\ldots,\mathtt{s_{n-1}}$ as edges to
$\textsc{Draw}(G_{\mathsf{pl}})$, where $\mathtt{s_{i}}$ represents the edge
between $v_{i}$ and $v_{i+1}$. Thus the edges corresponding to the $n-1$
strings $\mathtt{s_{1}},\mathtt{s_{2}},\ldots,\mathtt{s_{n-1}}$ constitute a
Hamiltonian path $(v_{1},v_{2},\ldots,v_{n})$ in $G_{\mathsf{pl}}$. This shows
(c).

Proof of (a): To show (a), we need to add all the edges of $G$ to
$G_{\mathsf{pl}}$ (other than those already added by the previous step), so
that $G_{\mathsf{pl}}$ becomes a supergraph of $G$. For each edge
$e=v_{i}v_{j}\in E(G)$, there are $k$ strings
$\mathtt{c}(u^{1}_{e}),\mathtt{c}(u^{2}_{e}),\ldots,\mathtt{c}(u^{k}_{e})$
(corresponding to the subdivision vertices
$u^{1}_{e},u^{2}_{e},\ldots,u^{k}_{e}$ in $G_{\mathsf{apex}}$) in $C$. Note
that for each $t\in\\{1,2,\ldots,k\\}$, the string $\mathtt{c}(u^{t}_{e})$
intersects exactly two other strings. Let $\mathtt{s}(u^{t}_{e})$ be the
substring of $\mathtt{c}(u^{t}_{e})$ between those two intersection points.
Let $\mathtt{s_{e}}$ be the string obtained by concatenating the $k$
substrings thus obtained.

$\mathtt{s_{e}}\triangleq\bigcup\limits_{t=1}^{k}\mathtt{s}(u^{t}_{e}).$ (19)

If the edge $e=v_{i}v_{j}$ is not already present in $G_{\mathsf{pl}}$, then
add the string $\mathtt{s_{e}}$ to $\textsc{Draw}(G_{\mathsf{pl}})$, where
$\mathtt{s_{e}}$ represents the edge between $v_{i}$ and $v_{j}$ (one end
point of $\mathtt{s_{e}}$ lies on $\mathtt{c}(v_{i})$ and the other on
$\mathtt{c}(v_{j})$). This completes the construction of
$\textsc{Draw}(G_{\mathsf{pl}})$, and shows (a).

Proof of (b): To show (b), it is enough to show that
$\textsc{Draw}(G_{\mathsf{pl}})$ is a planarizable representation of
$G_{\mathsf{pl}}$ (18). Note that there are three types of strings in
$\textsc{Draw}(G_{\mathsf{pl}})$: (i) substrings of $\mathtt{c}(a)$, (ii)
strings of the type $\mathtt{s_{e}}$, for some $e=v_{i}v_{j}\in E(G)$, and
(iii) $n$ strings corresponding to the original vertices of $G$.

Two strings of type (i) are either disjoint or intersect at their end points,
since $\mathtt{c}(a)$ is non-self-intersecting. More precisely, for each
$i\in[n-1]$, the point $p_{i+1}$ (the unique intersection point of
$\mathtt{s_{i}}$ and $\mathtt{s_{i+1}}$) lies on $\mathtt{c}(v_{i+1})$, which
denotes a vertex in $\textsc{Draw}(G_{\mathsf{pl}})$. A string of type (ii)
intersects exactly two strings, $\mathtt{c}(v_{i})$ and $\mathtt{c}(v_{j})$,
which denote vertices in $\textsc{Draw}(G_{\mathsf{pl}})$. Finally, strings of
type (iii) are mutually disjoint. This shows (b). ∎

###  3.3 Proof of Theorem 15 (b)

In this section, we will show that if $G$ is a yes-instance of Planar
Hamiltonian Path Completion, then $G_{\mathsf{apex}}$ is in Pure-2-Dir. In
other words, if $G$ is a subgraph of a planar graph with a Hamiltonian path,
then $G_{\mathsf{apex}}$ has a Pure-2-Dir representation.

First we elucidate the main idea behind our proof. Given a front line drawing
(Figure 2 (a)) of $G$, we will modify it to obtain a Pure-2-Dir representation
(Figure 2 (d)) of $G_{\mathsf{apex}}$. The apex segment $\mathtt{c}(a)$ takes
the place of the front line $\ell_{\mathsf{front}}$. The edges of $G$, which
were strings in the front line drawing, are replaced by rectilinear piecewise
linear curves. If we were allowed a large number of rectilinear pieces for
each edge, then this construction is trivial, since every curve can be viewed
as a series of infinitesimally small vertical and horizontal segments. Our
proof formally justifies that this can always be done when the number of
allowed rectilinear pieces is a fixed odd integer greater than or equal to
three.

###### Proof of 15 (b).

Given $G$, a yes-instance of Planar Hamiltonian Path Completion, we will
construct $C$, a Pure-2-Dir representation of $G_{\mathsf{apex}}$. Recall that
the construction of $G_{\mathsf{apex}}$ from $G$ uses an intermediate graph
$G_{k\operatorname{-{\mathsf{div}}}}$, where $k$ is an odd integer greater
than or equal to three.

$G\rightarrow G_{k\operatorname{-{\mathsf{div}}}}\rightarrow
G_{\mathsf{apex}}.$

Our proof is by induction on $k$. The major portion of this proof is for
$k=3$. At the end, we will show that if the proof works for $k$, then it also
works for $k+2$, and consequently for all odd integers $k\geq 3$.

#### Base case $(k=3)$:

Since $G$ is a subgraph of a planar graph with a Hamiltonian path (11), $G$
admits a front line drawing (Figure 2 (a)), as per 13. Our construction of $C$
(Figure 2 (d)) is based on and visually motivated by this drawing.

Let $n=|V(G)|$ and assume that $n\geq 4$. Let $(v_{1},v_{2},\ldots,v_{n})$ be
the ordering of the vertices on the front line $\ell_{\mathsf{front}}$ from
bottom to top. Let $E_{\mathsf{left}}$ be the set of edges that lie entirely
to the left of $\ell_{\mathsf{front}}$, $E_{\mathsf{right}}$ be the set of
edges that lie entirely to the right of $\ell_{\mathsf{front}}$, and
$E_{\mathsf{cross}}$ be the set of crossover edges (12). Further,
$E_{\mathsf{cross}}$ is the disjoint union of $E_{\mathsf{above}}$ and
$E_{\mathsf{below}}$, where $E_{\mathsf{above}}$ is the set of crossover edges
that go above $\ell_{\mathsf{front}}$, and $E_{\mathsf{below}}$ is the set of
crossover edges that go below $\ell_{\mathsf{front}}$. For example,
$v_{1}v_{3}\in E_{\mathsf{left}}$, $v_{2}v_{5}\in E_{\mathsf{right}}$ and
$v_{5}v_{7}\in E_{\mathsf{below}}$ in Figure 2 (a).

Given two points $p$ and $q$, we define $\ell(p,q)$ as the line segment
connecting them. Given an edge $e$, we define $\mathsf{area}(e)$ as the region
enclosed in the closed loop (including the boundary) defined by the union of
the edge $e=v_{i}v_{j}$ and the line segment $\ell(v_{j},v_{i})$. (Note that
$\ell(v_{j},v_{i})$ lies on $\ell_{\mathsf{front}}$.) This notion of area
induces a natural partial order “$\leq$” on the edges of $G$.

$e_{1}\leq
e_{2}\,\Longleftrightarrow\,\mathsf{area}(e_{1})\subseteq\mathsf{area}(e_{2}).$

For example, $v_{2}v_{6}\leq v_{2}v_{7}$ and $v_{4}v_{2}\leq v_{5}v_{7}$ in
Figure 2 (a). It is easy to see that $\leq$ is reflexive, anti-symmetric and
transitive. Thus, $(E,\leq)$ is a poset. Consider the Haase diagram of this
poset, where the minimal elements are placed at the bottom and the maximal
elements at the top. For an edge $e$, let $\mathsf{rank}(e)$ be the number of
elements (including $e$) on the longest downward chain starting from $e$. For
example, $\mathsf{rank}(v_{2}v_{7})=3$ because $v_{2}v_{5}\leq v_{2}v_{6}\leq
v_{2}v_{7}$ is the longest downward chain starting from $v_{2}v_{7}$ in Figure
2 (a). Note that the $\mathsf{rank}$ of all the minimal elements is one. We
are now all set to construct $C$, our Pure-2-Dir representation of
$G_{\mathsf{apex}}$ for $k=3$ (Figure 2 (d)).

The apex vertex $a$: Let $\mathtt{c}(a)$ be the vertical segment
$((0,0.5),(0,n+0.5))$. The vertices $\\{v_{1},v_{2},\ldots,v_{n}\\}$: For each
$i\in[n]$, let $\mathtt{c}(v_{i})$ be the horizontal segment
$((-a_{i}-0.1,i),(b_{i}+0.1,i))$, where $a_{i}$ and $b_{i}$ are defined as
follows. $\displaystyle a_{i}$
$\displaystyle=\max(\\{0\\}\cup\\{\mathsf{rank}(e)\mid e\text{ is incident to
$v_{i}$ and $e$ connects to $v_{i}$ from the left of
$\ell_{\mathsf{front}}$}\\});$ (20) $\displaystyle b_{i}$
$\displaystyle=\max(\\{0\\}\cup\\{\mathsf{rank}(e)\mid e\text{ is incident to
$v_{i}$ and $e$ connects to $v_{i}$ from the right of
$\ell_{\mathsf{front}}$}\\}).$ (21) The $\\{0\\}$ set is included to ensure
that the argument for the $\max$ operation is not an empty set. The vertices
$\\{u^{1}_{e},u^{2}_{e},u^{3}_{e}\\}$: For each edge $e$ of $G$, we define a
set of four points $\ell_{e}=(\alpha_{e},\beta_{e},\gamma_{e},\delta_{e})$,
such that $\displaystyle\mathtt{c}(u^{1}_{e})$
$\displaystyle=\ell(\alpha_{e},\beta_{e});$
$\displaystyle\mathtt{c}(u^{2}_{e})$
$\displaystyle=\ell(\beta_{e},\gamma_{e});$
$\displaystyle\mathtt{c}(u^{3}_{e})$
$\displaystyle=\ell(\gamma_{e},\delta_{e}).$ We may think of $\ell_{e}$ as a
piecewise linear curve with three pieces. Let
$\zeta:E\rightarrow\\{1,2,\ldots,n^{2}\\}$ be an injective function333One way
to formulate such a function is by setting $\zeta(e)=ni+j$ for each
$e=v_{i}v_{j}$, where $1\leq i<j\leq n$., i.e., $\zeta$ maps each edge $e$ of
$G$ to a distinct number from the set $\\{1,2,\ldots,n^{2}\\}$. For each edge
$e$, let $\mathsf{xpos}(e)=\mathsf{rank}(e)+\frac{\zeta(e)}{n^{4}}.$ (22) Let
$\varepsilon_{k}=1/(k^{2}n^{5})$ (for this construction, $k=3$). We use
$\mathsf{xpos}$ and $\varepsilon_{k}$ to define the four points of $\ell_{e}$,
for each $e$.
$\displaystyle\ell_{e}=\begin{cases}(\left(-\mathsf{xpos}(e),i\right),\left(-\mathsf{xpos}(e),\frac{i+j}{2}\right),\left(-\mathsf{xpos}(e)-\varepsilon_{k},\frac{i+j}{2}\right),\left(-\mathsf{xpos}(e)-\varepsilon_{k},j\right))&\text{if
}e\in E_{\mathsf{left}};\\\
(\left(\mathsf{xpos}(e),i\right),\left(\mathsf{xpos}(e),\frac{i+j}{2}\right),\left(\mathsf{xpos}(e)+\varepsilon_{k},\frac{i+j}{2}\right),\left(\mathsf{xpos}(e)+\varepsilon_{k},j\right))&\text{if
}e\in E_{\mathsf{right}};\\\
(\left(-\mathsf{xpos}(e),i\right),\left(-\mathsf{xpos}(e),n+\mathsf{rank}(e)\right),\left(\mathsf{xpos}(e),n+\mathsf{rank}(e)\right),\left(\mathsf{xpos}(e),j\right))&\text{if
}e\in E_{\mathsf{above}};\\\
(\left(-\mathsf{xpos}(e),i\right),\left(-\mathsf{xpos}(e),-\mathsf{rank}(e)\right),\left(\mathsf{xpos}(e),-\mathsf{rank}(e)\right),\left(\mathsf{xpos}(e),j\right))&\text{if
}e\in E_{\mathsf{below}}.\end{cases}$

Let $G_{\mathsf{rep}}$ be the intersection graph of $C$. We need to show that
$G_{\mathsf{apex}}=G_{\mathsf{rep}}$. First, let us understand the idea behind
our construction of $C$.

We consider each $\ell_{e}$ a single (piecewise linear) segment. Note that in
all four cases of its definition, $\ell_{e}$ always consists of two vertical
segments $\left(\mathtt{c}(u^{1}_{e}),\mathtt{c}(u^{3}_{e})\right)$ and one
horizontal segment $\left(\mathtt{c}(u^{2}_{e})\right)$. Also, the
x-coordinate of the vertical segments of $\ell_{e}$ is essentially the
$\mathsf{rank}$ (or the negation of the $\mathsf{rank}$) of $e$ (Equation 22).
The $\zeta(e)/n^{4}$ term (and also the $\varepsilon_{k}$ term) is simply a
tiny perturbation added to its x-coordinate to ensure that the vertical parts
of $\ell_{e}$ do not intersect the vertical parts of any other
$\ell_{e^{\prime}}$. ($\zeta$ was chosen to be an injection for precisely this
reason.)

Since $G_{\mathsf{apex}}$ and $G_{\mathsf{rep}}$ have the same vertex set, it
is sufficient to show that $e\in E(G_{\mathsf{apex}})\Leftrightarrow e\in
E(G_{\mathsf{rep}})$ in order to demonstrate their equality.

Proof of $e\in E(G_{\mathsf{apex}})\Rightarrow e\in E(G_{\mathsf{rep}})$: The
$\mathtt{c}(v_{i})$’s are horizontal segments, all intersecting the vertical
apex segment $\mathtt{c}(a)$. Further, the $\mathtt{c}(v_{i})$’s are made to
extend as far (to the left and right of $\mathtt{c}(a)$) as the maximum
$\mathsf{rank}$ (plus an additional $\pm 0.1$) of their incident edges
(Equation 20, Equation 21). This ensures that they intersect the vertical
segments of all their corresponding $\ell_{e}$’s. The fact that the
$\mathtt{c}(u^{1}_{e})$’s and $\mathtt{c}(u^{3}_{e})$’s intersect their
corresponding $\mathtt{c}(u^{2}_{e})$’s is implicit from the definition of
$\ell_{e}$.

Proof of $e\notin E(G_{\mathsf{apex}})\Rightarrow e\notin
E(G_{\mathsf{rep}})$: Note that $C$ has three types of segments: (i) the apex
($\mathtt{c}(a)$), (ii) the horizontal segments $\mathtt{c}(v_{i})$, and (iii)
the piecewise linear segments $\ell_{e}$. We will consider all pairs of non-
adjacent vertices $(p,q)$ of $G_{\mathsf{apex}}$, and show that
$\mathtt{c}(p)$ and $\mathtt{c}(q)$ do not intersect in $C$. We have three
cases.

Case 1: one of $\mathtt{c}(p)$ or $\mathtt{c}(q)$ is of type (i). Let us say
$\mathtt{c}(p)$ is of type (i), i.e., $p$ is the apex vertex $a$. Then
$\mathtt{c}(p)=((0,0.5),(0,n+0.5))$, and $\mathtt{c}(q)$ must be of type (iii)
(since all type (ii) vertices are adjacent to $a$). Note that the
x-coordinates of the vertical pieces of all the $\ell_{e}$’s in
$E_{\mathsf{left}}\cup E_{\mathsf{right}}$ are either less than $-0.1$ or
greater than $0.1$, and the y-coordinates of the horizontal pieces of all the
$\ell_{e}$’s in $E_{\mathsf{above}}\cup E_{\mathsf{below}}$ are either greater
than $n+0.5$ or less than $0.5$. Therefore, $\mathtt{c}(p)$ intersects none of
the $\ell_{e}$’s.

Case 2: one of $\mathtt{c}(p)$ or $\mathtt{c}(q)$ is of type (ii). Let us say
$\mathtt{c}(p)$ is of type (ii). If $\mathtt{c}(q)$ is also of type (ii), then
we are done, since all the $\mathtt{c}(v_{i})$’s are mutually disjoint
(Equation 20, Equation 21). If $\mathtt{c}(q)$ is of type (iii), then let
$\mathtt{c}(q)$ be a piece of $\ell_{e}$ for some edge $e$, and let $p=v_{k}$
for some $k\in[n]$ such that $e$ is not incident to $v_{k}$.

If $v_{k}\notin\mathsf{area}(e)$, then all segments of $\ell_{e}$ lie above
$\mathtt{c}(v_{k})$ or all segments of $\ell_{e}$ lie below
$\mathtt{c}(v_{k})$, implying that $\ell_{e}$ and $\mathtt{c}(v_{k})$ do not
intersect. If $v_{k}\in\mathsf{area}(e)$, then $\mathsf{area}(e)$ lies on at
least one of the sides (left/right) of $v_{k}\in\ell_{\mathsf{front}}$. Let
$e^{\prime}$ be an edge of maximum $\mathsf{rank}$ incident to $v_{k}$ such
that $e^{\prime}$ connects to $v_{k}$ from the same side (left/right) of
$\ell_{\mathsf{front}}$ as $\mathsf{area}(e)$. (If no such edge exists, then
the $\\{0\\}$ set (Equation 20, Equation 21) comes into play, and we are done,
as $\mathtt{c}(v_{k})$ falls short of $\ell_{e}$.) Recall that
$\mathsf{area}(e)$ comprises of $e$ and the front line
$\ell_{\mathsf{front}}$. Using the facts that $e^{\prime}$ does not cross $e$
or $\ell_{\mathsf{front}}$ and that $e^{\prime}$ connects to $v_{k}$ from the
interior of $\mathsf{area}(e)$, we obtain that $e^{\prime}$ lies entirely
inside $\mathsf{area}(e)$. Therefore,

$\mathsf{area}(e^{\prime})\subseteq\mathsf{area}(e)\ \Rightarrow\
e^{\prime}\leq e\ \Rightarrow\ \mathsf{rank}(e^{\prime})<\mathsf{rank}(e)\
\Rightarrow\ \mathsf{rank}(e^{\prime})+1\leq\mathsf{rank}(e).$

Note that the vertical pieces of $\ell_{e}$ are at least $\mathsf{rank}(e)$
units away from the apex segment $\mathtt{c}(a)$, and the horizontal segment
$\mathtt{c}(v_{k})$ only reaches as far as
$\mathsf{rank}(e^{\prime})+0.1<\mathsf{rank}(e)$ units from $\mathtt{c}(a)$ in
the direction of $\ell_{e}$. Thus, $\mathtt{c}(v_{k})$ and $\ell_{e}$ do not
intersect. Also, all the horizontal pieces of $\ell_{e}$ of
non-$\varepsilon_{k}$ length belong to edges of $E_{\mathsf{cross}}$, which
lie above $\mathtt{c}(a)$ or below $\mathtt{c}(a)$, and thus none of them
intersect $\mathtt{c}(v_{k})$.

Case 3: both $\mathtt{c}(p)$ and $\mathtt{c}(q)$ are of type (iii). Let
$\mathtt{c}(p)$ be a piece of $\ell_{e_{p}}$ and $\mathtt{c}(q)$ be a piece of
$\ell_{e_{q}}$, for some edges $e_{p}$ and $e_{q}$ of $G$. If they are both
vertical pieces or one of them is a horizontal piece of length
$\varepsilon_{k}$, then the $\zeta$ function guarantees that they do not
intersect.

Thus, the only remaining case is if one of them (say $\mathtt{c}(p)$) is a
horizontal piece of non-$\varepsilon_{k}$ length (i.e., $e_{p}$ is a crossover
edge). Let $e_{p}\in E_{\mathsf{above}}$ (the proof for $e_{p}\in
E_{\mathsf{below}}$ is similar). The y-coordinate of $\mathtt{c}(p)$ is
greater than $n+0.5$. If $e_{q}\in E_{\mathsf{left}}\cup
E_{\mathsf{right}}\cup E_{\mathsf{below}}$, then all segments of
$\ell_{e_{q}}$ lie below $\mathtt{c}(p)$, and we are done. If $e_{q}\in
E_{\mathsf{above}}$, then note that the all the edges contained in
$E_{\mathsf{above}}$ constitute a total order (or chain) in the poset
$(E,\leq)$. Thus either $\mathsf{rank}(e_{p})<\mathsf{rank}(e_{q})$ or
$\mathsf{rank}(e_{q})<\mathsf{rank}(e_{p})$. Let
$\mathsf{rank}(e_{p})<\mathsf{rank}(e_{q})$ (the proof for
$\mathsf{rank}(e_{q})<\mathsf{rank}(e_{p})$ is similar). All the pieces of
$\ell_{e_{q}}$ are at least $\mathsf{rank}(e_{p})+0.5$ units away from the
apex segment $\mathtt{c}(a)$, and all the pieces of $\ell_{e_{q}}$ reach less
than $\mathsf{rank}(e_{p})+0.1$ units away from $\mathtt{c}(a)$. Hence,
$\ell_{e_{p}}$ and $\ell_{e_{q}}$ do not intersect.

This completes the proof of the base case ($k=3$) of our induction. A crucial
feature of our construction, which we will exploit in our proof of the
inductive case, is that for all edges $e$ of $G$, the segment
$\mathtt{c}(u^{3}_{e})$ is a vertical segment.

#### Induction hypothesis:

Let $k\geq 3$ be an odd integer. Then there exists a Pure-2-Dir representation
of $G_{\mathsf{apex}}$ in which $\mathtt{c}(u^{k}_{e})$ is a vertical segment
for all edges $e$ of $G$.

#### Induction step:

Given a Pure-2-Dir representation of $G_{\mathsf{apex}}$ where
$\mathtt{c}(u^{k}_{e})$ is a vertical segment, we will slightly modify it to
include two new segments $\mathtt{c}(u^{k+1}_{e})$ and
$\mathtt{c}(u^{k+2}_{e})$ for each $e$, such that $\mathtt{c}(u^{k+2}_{e})$ is
a vertical segment. Let

$\displaystyle\mathtt{c}(u^{k}_{e})$
$\displaystyle=((\lambda^{k}_{e},\mu^{k}_{e}),(\lambda^{k}_{e},\pi^{k}_{e}));$
$\displaystyle\sigma^{k+2}_{e}$ $\displaystyle=\begin{cases}-1\qquad\text{ if
}\lambda^{k}_{e}<0;\\\ +1\qquad\text{ if }\lambda^{k}_{e}>0.\end{cases}$

Recall that $\varepsilon_{k}=1/(k^{2}n^{5})$. Now for each edge $e$ of $G$, we
replace the segment $\mathtt{c}(u^{k}_{e})$ by the following three segments.

$\displaystyle\mathtt{c}(u^{k}_{e})$
$\displaystyle=\displaystyle{\left(\left(\lambda^{k}_{e},\mu^{k}_{e}\right),\left(\lambda^{k}_{e},\frac{\mu^{k}_{e}+\pi^{k}_{e}}{2}\right)\right)};$
$\displaystyle\mathtt{c}(u^{k+1}_{e})$
$\displaystyle=\displaystyle{\left(\left(\lambda^{k}_{e},\frac{\mu^{k}_{e}+\pi^{k}_{e}}{2}\right),\left(\lambda^{k}_{e}+\sigma^{k+2}_{e}\varepsilon_{k+2},\frac{\mu^{k}_{e}+\pi^{k}_{e}}{2}\right)\right)};$
$\displaystyle\mathtt{c}(u^{k+2}_{e})$
$\displaystyle=\displaystyle{\left(\left(\lambda^{k}_{e}+\sigma^{k+2}_{e}\varepsilon_{k+2},\frac{\mu^{k}_{e}+\pi^{k}_{e}}{2}\right),\left(\lambda^{k}_{e}+\sigma^{k+2}_{e}\varepsilon_{k+2},\pi^{k}_{e}\right)\right)}.$

Note that these three new segments roughly coincide with the segment that they
replaced, with a tiny perturbation of $\sigma^{k+2}_{e}\varepsilon_{k+2}$ made
to the x-coordinates of $\mathtt{c}(u^{k+1}_{e})$ and
$\mathtt{c}(u^{k+2}_{e})$. Using the induction hypothesis, it is easy to see
that $\mathtt{c}(u^{k}_{e})$, $\mathtt{c}(u^{k+1}_{e})$ and
$\mathtt{c}(u^{k+2}_{e})$ intersect the segments that they are adjacent to in
$G_{\mathsf{apex}}$. The following calculation shows that the
$\sigma^{k+2}_{e}\varepsilon_{k+2}$ perturbation is so minuscule that
$\mathtt{c}(u^{k+1}_{e})$ and $\mathtt{c}(u^{k+2}_{e})$ do not intersect any
additional segments.

$\displaystyle{\left|\sum_{i=3}^{k+2}\sigma^{i}_{e}\varepsilon_{i}\right|\leq\frac{1}{n^{5}}\left(\sum_{i=3}^{k+2}\frac{1}{i^{2}}\right)<\frac{1}{n^{5}}}.$

Note that for every $e^{\prime}\neq e$ and every odd $k^{\prime}$ such that
$1\leq k^{\prime}\leq k+2$, the x-coordinates of
$\mathtt{c}(u^{k^{\prime}}_{e^{\prime}})$ and $\mathtt{c}(u^{k}_{e})$ differ
by roughly $1/n^{4}$, which is much larger than $1/n^{5}$. Finally, note that
$\mathtt{c}(u^{k+2}_{e})$ is a vertical segment, as promised. This completes
the proof. ∎

##  4 Planarizable Representations of Planar Graphs

In this section, we will show 18, i.e., a graph admits a planarizable
representation (17) if and only if the graph is planar.

###### Proof of 18.

It is easy to see that every planar graph admits a planarizable
representation. We will show the other direction: every graph that admits a
planarizable representation is planar. Let $G$ be a graph with a planarizable
representation. Let $v$ be a vertex of $G$, and $\mathtt{c}(v)$ be its
corresponding string. Figure 5 shows the steps of our proof for a given
$\mathtt{c}(v)$. Let

$R_{v}=\\{p\mid p\in\mathbb{R}^{2},d(p,\mathtt{c}(v))\leq\varepsilon\\}$

be the set of points within a closed $\varepsilon$-neighbourhood of
$\mathtt{c}(v)$, choosing $\varepsilon$ small enough so that $\mathtt{c}(v)$
does not intersect any additional strings. Delete all substrings lying in the
interior of $R_{v}$. Thus all strings that intersected $\mathtt{c}(v)$ now
have one end point on the boundary of $R_{v}$. Connect all these boundary end
points to a common point (say $p_{v}$) in the interior of $R_{v}$ via pairwise
disjoint substrings (intersecting only at $p_{v}$) in the interior of $R_{v}$,
effectively “shrinking” the region $R_{v}$ to a single point $p_{v}$. (This
last step is possible because $R_{v}$ is a simply connected region.) Now the
point $p_{v}$ corresponds to the vertex $v$.

Do this for all the vertices of $G$. Since the vertices are now points, and
the edges are strings connecting them, the representation thus obtained is a
planar drawing of $G$. ∎

$p_{v}$$p_{v}$$\mathtt{c}(v)$$R_{v}$$R_{v}$$\xrightarrow{\ (i)\
}$$\xrightarrow{\ (ii)\ }$$\xrightarrow{\ (iii)\ }$

Figure 5: Initially, the vertex $v$ is denoted by the blue string
$\mathtt{c}(v)$, and the edges incident to it are denoted in red. (i)
$\mathtt{c}(v)$ is “thickened” to form a region $R_{v}$ around it. (ii) The
end points of the edges on the boundary of $R_{v}$ are connected to a single
point $p_{v}$ in the interior of $R_{v}$. (iii) Strings that share an end
point on the boundary of $R_{v}$ are concatenated, and the region $R_{v}$ is
“shrunk” to the point $p_{v}$.

##  5 Conclusion

8 states that recognizing rectangle intersection graphs is $\NP$-hard, even
when the inputs are bipartite apex graphs. This raises the following question.
Can we recognize planar rectangle intersection graphs in polynomial time? As
mentioned earlier, all planar graphs are intersection graphs of 3-dimensional
hyper-rectangles (or axis-parallel cuboids) [Tho86, FF11]. Furthermore, there
exist series-parallel graphs (a subclass of planar graphs) that are not
rectangle intersection graphs [BCR06].

9 states that for all graph classes $\mathcal{G}$ such that
$\textup{{Pure-2-Dir}}\subseteq\mathcal{G}\subseteq\textup{{1-String}}$, the
recognition of $\mathcal{G}$ is not FPT (fixed-parameter tractable), when
parameterized by the apex number of the graph. As our construction produces
graphs of large degree, the maximum degree of the graph might be a parameter
for which the recognition of $\mathcal{G}$ is FPT.

10 states that recognizing several geometric intersection graph classes is
$\NP$-hard, even when the inputs are restricted to $K_{6}$-minor free graphs.
On the other hand, the complexity of finding geometric representations of
$K_{5}$-minor free graphs is unknown. Is it possible to use Wagner’s Theorem
[Wag37] to decide in polynomial time whether a $K_{5}$-minor free graph is in
1-String (or String)? It would also be interesting to study the complexity of
recognizing String when the inputs are restricted to apex graphs.

The crossing number of a graph is the minimum number of edge crossings
possible in a plane drawing of the graph. Planar graphs are precisely the
graphs with crossing number zero. Schaefer showed that apex graphs can have
arbitrarily high crossing number, and also exhibited several graphs with
crossing number one [Sch18]. Graph classes with a small crossing number, like
$k$-planar graphs [ABB+20], have also been studied. Therefore, the complexity
of recognizing 1-String (or String) when the inputs are restricted to graphs
with a small crossing number is another potential direction of research.

Finally, it would be interesting to see if our techniques can be used to prove
$\NP$-hardness of recognizing other classes of geometric intersection graphs,
like outerstring graphs [BBD18] and intersection graphs of grounded L-shapes
[McG96]. Also, the graph classes we study in this paper are for objects
embedded in the plane. The complexity of finding geometric intersection
representations of apex graphs (appropriately defined) using curves on other
surfaces (e.g., torus, projective plane) is another avenue open for
exploration.

Acknowledgements: This project has received funding from the European Union’s
Horizon 2020 research and innovation programme under grant agreement No.
682203-ERC-[Inf-Speed-Tradeoff]. The authors thank the organisers of
Graphmasters 2020 [GKR20] for providing the virtual environment that initiated
this research.

## References

  * [ABB+20] P. Angelini, M. A. Bekos, F. J. Brandenburg, G. Da Lozzo, G. Di Battista, W. Didimo, M. Hoffmann, G. Liotta, F. Montecchiani, I. Rutter, and C. D. T/’oth.  Simple k-planar graphs are simple (k+ 1)-quasiplanar.  Journal of Combinatorial Theory, Series B, 142:1–35, 2020.
  * [AG11] 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.
  * [AH77] K. Appel and W. Haken.  The solution of the four-color-map problem.  Scientific American, 237(4):108–121, 1977.
  * [And70] EM Andreev.  On convex polyhedra in lobacevskii spaces.  Mathematics of the USSR-Sbornik, 10(3):413, 1970.
  * [AVK98] P. K. Agarwal and M. J. Van Kreveld.  Label placement by maximum independent set in rectangles.  Elsevier, 1998.
  * [BBD18] T. Biedl, A. Biniaz, and M. Derka.  On the size of outer-string representations.  In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [BCR06] A. Bohra, L. S. Chandran, and J. K. Raju.  Boxicity of series-parallel graphs.  Discrete mathematics, 306(18):2219–2221, 2006.
  * [Ben59] S. Benzer.  On the topology of the genetic fine structure.  Proceedings of the National Academy of Sciences of the United States of America, 45(11):1607, 1959.
  * [BL76] K. S. Booth and G. S. Lueker.  Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms.  Journal of computer and system sciences, 13(3):335–379, 1976.
  * [CG09] J. Chalopin and D. Gonçalves.  Every planar graph is the intersection graph of segments in the plane.  In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 631–638, 2009.
  * [CGO10] J. Chalopin, D. Gonçalves, and P. Ochem.  Planar graphs have 1-string representations.  Discrete & Computational Geometry, 43(3):626–647, 2010.
  * [Chm20] P. Chmel.  Algorithmic aspects of intersection representations.  Bachelors Thesis, 2020.
  * [CJ17] S. Cabello and M. Jejčič.  Refining the hierarchies of classes of geometric intersection graphs.  the electronic journal of combinatorics, pages P1–33, 2017.
  * [CJKV12] S. Chaplick, V. Jelínek, J. Kratochvíl, and T. Vyskočil.  Bend-bounded path intersection graphs: Sausages, noodles, and waffles on a grill.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 274–285. Springer, 2012.
  * [CLR83] 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.
  * [CLR84] F.R.K Chung, F.T. Leighton, and A.L. Rosenberg.  A graph layout problem with applications to VLSI design, 1984.
  * [DCCD+99] N. De Castro, F. J. Cobos, J. C. Dana, A. Márquez, and M. Noy.  Triangle-free planar graphs as segments intersection graphs.  In International Symposium on Graph Drawing, pages 341–350. Springer, 1999.
  * [DF12] Rodney G Downey and Michael Ralph Fellows.  Parameterized complexity.  Springer Science & Business Media, 2012.
  * [FF11] S. Felsner and M. C. Francis.  Contact representations of planar graphs with cubes.  In Proceedings of the twenty-seventh annual symposium on Computational geometry, pages 315–320, 2011.
  * [GI91] Arvind Gupta and Russell Impagliazzo.  Computing planar intertwines.  In FOCS, pages 802–811. Citeseer, 1991.
  * [GIP18] D. Gonçalves, L. Isenmann, and C. 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. SIAM, 2018.
  * [GKR20] Leszek Ga̧sieniec, Ralf Klasing, and Tomasz Radzik.  Combinatorial Algorithms: 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Proceedings, volume 12126.  Springer Nature, 2020.
  * [GLP19] D. Gonçalves, B. Lévêque, and A. Pinlou.  Homothetic triangle representations of planar graphs.  Journal of Graph Algorithms and Applications, 23(4):745–753, 2019\.
  * [Gon19] D. Gonçalves.  3-colorable planar graphs have an intersection segment representation using 3 slopes.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 351–363. Springer, 2019.
  * [Gon20] D. Gonçalves.  Not all planar graphs are in pure-4-dir.  Journal of Graph Algorithms and Applications, 24(3):293–301, 2020\.
  * [Had75] Frank Hadlock.  Finding a maximum cut of a planar graph in polynomial time.  SIAM Journal on Computing, 4(3):221–225, 1975.
  * [HNZ91] I. B. Hartman, I. Newman, and R. Ziv.  On grid intersection graphs.  Discrete Mathematics, 87(1):41–52, 1991.
  * [HW74] John E Hopcroft and Jin-Kue Wong.  Linear time algorithm for isomorphism of planar graphs (preliminary report).  In Proceedings of the sixth annual ACM symposium on Theory of computing, pages 172–184, 1974.
  * [KM89] J. Kratochvíl and J. Matoušek.  NP-hardness results for intersection graphs.  Commentationes Mathematicae Universitatis Carolinae, 30(4):761–773, 1989.
  * [Koe36] P. Koebe.  Kontaktprobleme der konformen Abbildung.  Hirzel, 1936.
  * [KP07] J. Kratochvíl and M. Pergel.  Geometric intersection graphs: do short cycles help?  In International Computing and Combinatorics Conference, pages 118–128. Springer, 2007.
  * [Kra91] J. Kratochvíl.  String graphs. II. recognizing string graphs is NP-hard.  Journal of Combinatorial Theory, Series B, 52(1):67–78, 1991.
  * [Kra94] J. Kratochvíl.  A special planar satisfiability problem and a consequence of its NP-completeness.  Discrete Applied Mathematics, 52(3):233–252, 1994.
  * [KWZ08] F. Kuhn, R. Wattenhofer, and A. Zollinger.  Ad hoc networks beyond unit disk graphs.  Wireless Networks, 14(5):715–729, 2008.
  * [LT79] R. J. Lipton and R. E. Tarjan.  A separator theorem for planar graphs.  SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.
  * [McG96] S. McGuinness.  On bounding the chromatic number of L-graphs.  Discrete Mathematics, 154(1-3):179–187, 1996.
  * [MP19] 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\.
  * [Nie06] Rolf Niedermeier.  Invitation to fixed-parameter algorithms.  OUP Oxford, 2006.
  * [RS04] Neil Robertson and Paul D Seymour.  Graph minors. xx. wagner’s conjecture.  Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004\.
  * [Sch84] E. R. Scheinerman.  Intersection classes and multiple intersection parameters of graphs.  Princeton University, 1984.
  * [Sch18] M. Schaefer.  Crossing numbers of graphs.  CRC Press, 2018.
  * [She07] N. A. Sherwani.  Algorithms for VLSI Physical Design Automation.  Springer US, 2007.
  * [Sin66] F. W. Sinden.  Topology of thin film rc circuits.  Bell System Technical Journal, 45(9):1639–1662, 1966.
  * [SSŠ03] M. Schaefer, E. Sedgwick, and D. Štefankovič.  Recognizing string graphs in NP.  Journal of Computer and System Sciences, 67(2):365–380, 2003.
  * [Sto73] Larry Stockmeyer.  Planar 3-colorability is polynomial complete.  ACM Sigact News, 5(3):19–25, 1973.
  * [TB97] 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.
  * [Tho86] C. Thomassen.  Interval representations of planar graphs.  Journal of Combinatorial Theory, Series B, 40(1):9–20, 1986.
  * [Thu82] William Thurston.  Hyperbolic geometry and 3-manifolds.  Low-dimensional topology (Bangor, 1979), 48:9–25, 1982.
  * [Tut63] W. T. Tutte.  How to draw a graph.  Proceedings of the London Mathematical Society, 3(1):743–767, 1963\.
  * [Wag37] K. Wagner.  Über eine eigenschaft der ebenen komplexe.  Mathematische Annalen, 114(1):570–590, 1937.
  * [Wel93] D. J. A. Welsh.  Knots and braids: some algorithmic questions.  Contemporary Mathematics, 147, 1993.
  * [Wes91] D. West.  Open problems.  SIAM J. Discrete Math. Newslett., 2(1):10–12, 1991.
  * [Wig82] A. Wigderson.  The complexity of the hamiltonian circuit problem for maximal planar graphs.  Technical report, Tech. Rep. EECS 198, Princeton University, USA, 1982\.
  * [XB06] J. Xu and B. Berger.  Fast and accurate algorithms for protein side-chain packing.  Journal of the ACM (JACM), 53(4):533–557, 2006.