[gray,opacity=0.3] (0.6,0.8)–(0.5,1.7)–(0.7,2.4)–(0.9,2.2)–(0.7,1.7)–(0.8,0.6);

[gray,opacity=0.3] (-0.8,-0.6)–(-1.6,-0.5)–(-2.4,-0.7)–(-2.2,-0.9)–(-1.6,-0.7)–(-0.6,-0.8);

[gray,opacity=0.3] (0.8,-0.6)–(1.6,-0.5)–(2.4,-0.7)–(2.2,-0.9)–(1.6,-0.7)–(0.6,-0.8);

[gray,opacity=0.3] (-0.9,3.8)–(0,4)–(0.9,3.8)–(0.7,3.6)–(0,3.8)–(-0.7,3.6);

[gray,opacity=0.3] (-2.3,2.4)–(-3,2.4)–(-3.5,1.5)–(-3.5,0.5)–(-3.8,-0.2)–(-3.8,-0.9)–(-3.6,-0.7)–(-3.6,-0.2)–(-3.3,0.3)–(-3.3,1.3)–(-2.8,2.2)–(-2.1,2.2);

[gray,opacity=0.3] (-2.1,3.8)–(-1.7,5)–(-0.6,5.2)–(-0.8,5.4)–(-1.9,5.2)–(-2.3,3.6);

[gray,opacity=0.3] (2.1,3.8)–(1.7,5)–(0.6,5.2)–(0.8,5.4)–(1.9,5.2)–(2.3,3.6);

[gray,opacity=0.3] (2.3,2.4)–(3,2.4)–(3.5,1.5)–(3.5,0.5)–(3.8,-0.2)–(3.8,-0.9)–(3.6,-0.7)–(3.6,-0.2)–(3.3,0.3)–(3.3,1.3)–(2.8,2.2)–(2.1,2.2);

[gray,opacity=0.3] (-2.2,-2.1)–(-1.5,-2.1)–(-0.5,-2.3)–(0.5,-2.3)–(1.5,-2.1)–(2.2,-2.1)–(2.4,-2.3)–(1.5,-2.3)–(0.5,-2.5)–(-0.5,-2.5)–(-1.5,-2.3)–(-2.4,-2.3);

[gray,opacity=0.3] (-3.8,-2.1)–(-4.5,-2.1)–(-4.5,-1.1)–(-4,-0.5)–(-4.5,0.5)–(-4,1.5)–(-4.5,2.5)–(-4,3.5)–(-4.5,4.5)–(-4,5.5)–(-3,6)–(-2,5.5)–(-1.8,6.6)–(-1.2,6.8)–(-0.8,6.6)–(-0.6,6.8)–(-1.2,7)–(-2,6.8)–(-2.2,5.8)–(-3.2,6.2)–(-4.2,5.5)–(-4.7,4.5)–(-4.2,3.5)–(-4.7,2.5)–(-4.2,1.5)–(-4.7,0.5)–(-4.2,-0.5)–(-4.7,-1.1)–(-4.7,-2.3)–(-3.6,-2.3);

[gray,opacity=0.3] (3.8,-2.1)–(4.5,-2.1)–(4.5,-1.1)–(4,-0.5)–(4.5,0.5)–(4,1.5)–(4.5,2.5)–(4,3.5)–(4.5,4.5)–(4,5.5)–(3,6)–(2,5.5)–(1.8,6.6)–(1.2,6.8)–(0.8,6.6)–(0.6,6.8)–(1.2,7)–(2,6.8)–(2.2,5.8)–(3.2,6.2)–(4.2,5.5)–(4.7,4.5)–(4.2,3.5)–(4.7,2.5)–(4.2,1.5)–(4.7,0.5)–(4.2,-0.5)–(4.7,-1.1)–(4.7,-2.3)–(3.6,-2.3);

(a) An example 4-regular planar graph, and (b) the polygon that corresponds to the graph given in (a).

§.§.§ The time and space complexity.
Given a 4-regular planar graph $H$ on $n$ vertices, we add $n$ chambers to $P$, each having 12 vertices. The positions of the centers of chambers can be determined with respect to any planar embedding of $H$. For each pair of adjacent vertices in $H$, we add a corridor to $P$ between the chambers corresponding to these vertices. The number of vertices on each polygonal chain of a corridor is at most $O(n)$, therefore at most $O(n + n) = O(n)$ vertices in a corridor, in total. Thus, both chambers and corridors take up polynomial space. Since there are $2n$ edges in $H$, there are at most $O(n + 2n^2) = O(n^2)$ vertices in $P$, thus polynomially many edges in $P$. As a result, the given reduction can be done in polynomial time and space.

As we proved the correctness of our reduction and showed that it is a polynomial-time reduction, the theorem holds. Since the 3-coloring problem for 4-regular planar graphs is NP-complete [37], the  3-coloring problem for unit disk visibility graphs of polygons with holes is also NP-complete.

Since the 3-coloring problem for 4-regular planar graphs is NP-complete [37], the 3-coloring problem for unit disk visibility graphs of polygons with holes is also NP-complete by Theorem <ref>.

§ SOME OTHER COMBINATORIAL PROBLEMS ON UNIT DISK VISIBILITY GRAPHS

In previous sections, we considered the 3-coloring problem (in general, chromatic number problem) for the unit disk visibility graphs of a set of line segments, and a set of points.
There are of course many other combinatorial problems to consider.
In this section, our aim is to give some insight about some other famous combinatorial problems, and argue why it would be interesting to study them.

In the gadget used to prove NP-completeness of 3-coloring of unit disk segment visibility graphs, all line segments can be exactly one unit long except the edge crossings. Moreover, the rest of the gadget contains line segments either horizontal or vertical (parallel to $x$ or $y$-axis). Considering these facts, we pose these two interesting questions for reader's consideration:

Is the 3-colorability of unit disk visibility graphs of line segments NP-hard when all the segments are exactly 1 unit long?

Is the 3-colorability of unit disk visibility graphs of line segments NP-hard when all the segments are either vertical or horizontal?

As the above results show that unit disk visibility graphs are not included in the (hierarchic) intersection of unit disk graphs and visibility graphs, we would like to study the following problems which may have interesting results on unit disk visibility graphs.

Maximum clique problem on unit disk visibility graphs.

It is a long known result that the maximum clique problem of a unit disk graph can be found in polynomial time when the representation is given [28] and even without a representation [101].
However, the algorithm described by Clark et al. [28] relies on the fact that if two disk centers are close enough, then the corresponding disks intersect, and thus the corresponding vertices are adjacent.
Whereas for unit disk visibility graph, this is not the case.
Even though two disk centers are close enough, there might be an obstacle in-between, which means the corresponding vertices might not be adjacent.
It is therefore an interesting problem to study for unit disk visibility graphs.

Chromatic number problem on unit disk visibility graphs of polygons.

In Section <ref>, we showed that the determining whether a visibility graph of a set of line segments is 3-colorable is NP-complete.
These reductions are possible because of the edge-crossing certificates (see Figure <ref> and Figure <ref>).
In the certificates, we use a special structure in the middle of the gadget, to transfer the colors properly.
Specifically, this structure is $W_4$: consists of five vertices: $a,b,c,d,e$ and 8 edges $ab, bc, cd, da, ea, eb, ec, ed$.
In Section <ref>, it was proven that deciding whether the visibility graph of a simple polygon is 4-colorable can be done in polynomial time, and 5-colorability problem is NP-complete.
The complexity of deciding the 3-colorability (even 4-colorability) for the unit disk visibility graph of a simple polygon is yet to be solved.

Determining whether a unit disk visibility graph of segments yields a Hamiltonian cycle.

Hoffman and Tóth showed that every segment visibility graph yields a Hamiltonian cycle [71].
It is clearly not the case for unit disk visibility graphs of segments (consider two segments with entpoints on $(0,0)$, $(1,0)$, $(0,1)$, $(0,2)$).
Thus, we ask the question: can we determine whether a unit disk visibility graph of line segments yield a Hamiltonian cycle in polynomial time?

Conflict-free coloring problem on a unit disk visibility graph of segments, a unit disk visibility graph of points, and a unit disk visibility graph of polygons.

A correct solution to the conflict-free coloring problem on a graph is assigning colours to (not necessarily all) vertices of that graph such that the neighborhood of each vertex contains at least one unique color [106].
This problem is shown to be NP-hard for the visibility graphs of simple polygons in Section <ref>.
To the best of our knowledge, the problem is open for the visibility graphs of a set of points, and the visibility graphs of line segments.
As for the unit disk graphs, it is NP-complete to decide whether a conflict-free coloring with only one color exists, and six colors are always sufficient [51].
However, as we mentioned in Section <ref>, the result for the unit disk graphs does not apply to unit disk visibility graphs.
All considered, studying the conflict-free coloring problem for UDVG of segments, UDVG of points, and UDVG of polygons is an interesting research direction.

CHAPTER: AXES-PARALLEL UNIT DISK GRAPHS

§ SUMMARY OF THE CHAPTER

In this chapter, we first describe a polynomial-time reduction which shows that deciding whether a graph can be realized as unit disks onto given straight lines is NP-hard,
when the given lines are parallel to either $x$-axis or $y$-axis.
Using the reduction we described, we also show that this problem is NP-complete when the given lines are only parallel to $x$-axis (and one another).
We obtain those results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987.

* If the disks are forced to be centered on straight lines of which any pair is either parallel or perpendicular, then the recognition problem is NP-hard.

* If any pair of the pre-given lines are parallel to each other, then the problem is NP-complete.

* If there are only two lines that are perpendicular, then the recognition problem is interesting to study, yet does not yield trivial results.

§ RELATED WORK

In this chapter, we are particularly interested in the unit disk graph recognition problem i.e. given a simple graph, deciding whether there exists an embedding of disks onto the plane whose intersections corresponds to the given graph.

Breu and Kirkpatrick showed that the unit disk graph recognition problem is NP-hard in general[19].
Later on, this result was extended, and it was proved that the problem is also $\exists\mathbb{R}$-complete [83, 93].
Aspnes et al. showed that, even when we know the precise pairwise distances between the adjacent vertices in a unit disk graph, it is NP-hard to find a unique embedding of unit disks [9][Note that this problem is different than embeddability of an edge weighted graph [102], since two disks must intersect if their centers are close enough.].
Kuhn et al. showed that finding a “good” embedding is not approximable when the problem is parameterized by the maximum distance between any pair of disks' centers [84].
Besides the recognition problem, there are other famous combinatorial problems that remain NP-hard when the input graph is a unit disk graph.
Some of these problems are, but not limited to, maximum independent set [28], $k$-coloring [64], minimum dominating set [92],  and Hamiltonian cycle [74].

Ito and Kadoshita tackled the above mentioned problems by assuming that the centers of disks are in a predefined square-shaped region [73].
They found out that some of these problems, namely, Hamiltonian cycle and $k$-coloring are fixed-parameter tractable, whereas some other problems, namely, the maximum independent set and the minimum dominating set are both W[1]-complete.
The result of [73] is a nice example to show that restricting the domain does not cause radical changes on the complexities of all major combinatorial problems.
But how does the recognition problem behave when the domain is restricted?

Intuitively, the most restricted domain for unit disk graphs is when the disks are centered on a single straight line in the Euclidean plane.
In this case, the unit disks become unit intervals on the line, and they yield a unit interval graph [91].
To recognize whether a given graph is a unit interval graph is a linear-time task [24].
Breu studied the problem of unit disk graph recognition when each disk is centered on a “thick line” of width $c$ [23].
In other words, the disks are restricted to be centered in the area between two straight lines with Euclidean distance $c$.
Such a configuration is called a $c$-strip graph.
He showed that the recognition problem can be solved in polynomial time with this constraint, when $c \leq \sqrt{3}/2$.
That is, the mapping function for a given unit disk graph $G = (V,E)$ is $\Sigma: V \to (-\infty,+\infty) \times (0,c)$ where $0 \leq c \leq \sqrt{3}/2$.
Later on, Hayashi et al. introduced the class of thin strip graphs [68].
A graph is a thin strip graph, if it is a $c$-strip graph for every $c>0$.
The main result of [68] is that no constant $t$ exists where the $t$-strip graphs are exactly thin strip graphs.

In our work, we introduce axes-parallel unit disk graphs.
Our domain is restricted to the set of straight lines given by their equations.
Given a simple graph, and a set of straight lines, we ask the question “can this graph be realized as unit disks on the given straight lines?”
The answer to this question is “yes” if the given graph can be realized as unit disks, onto the straight lines that are given as input.
We show that even though these lines are restricted to be parallel to either $x$-axis or $y$-axis, it is NP-hard to recognize whether $G$ is an axes-parallel unit disk graph.

§ APUD(K,M) RECOGNITION

We prove that axes-parallel unit disk recognition ($\APUD(k,m)$ recognition with $k$ and $m$ given as input) is NP-hard by giving reduction from the Monotone not-all-equal 3-satisfiability (NAE3SAT) problem[This problem is equivalent to the 2-coloring of 3-uniform hypergraphs. We choose to give the reduction from Monotone NAE3SAT as it is more intuitive to construct for our problem].
NAE3SAT is a variation of 3SAT a satisfying assignment must not give the thee literals in each clause the same truth value, and due to Schaefer's dichotomy theory, The problem remains NP-complete when all clauses are monotone (i.e. none of the literals are negated) [103].
Our main theorem is as follows.

There is a polynomial-time reduction of any instance $\Phi$ of Monotone NAE3SAT to some instance $\Psi$ of $\APUD(k,m)$ such that $\Phi$ is a YES-instance if, and only if $\Psi$ is a YES-instance.

We construct our hardness proof using the scheme called a logic engine, which is used to prove the hardness of several geometric problems [11].
For a given instance $\Phi$ of Monotone NAE3SAT, there are two main components in our reduction.
First, we construct a backbone for our gadget.
The backbone models only the number of clauses and the number of literals.
Next, we model the relationship between the clauses and literals, i.e. which literal appears in which clause.

Let us begin by describing the input graph.
For the sake of simplicity, we assume that the given formula has $3$ clauses, $A, B, C$, and $4$ literals, $q,r,s,t$ for the moment.
In general, we denote the clauses by $C_1, \dots, C_k$, and the literals by $x_1, \dots, x_m$.
Later on, with the help of Figure <ref>, we explain how to generalize the input graph according to any given instance of Monotone NAE3SAT formula.
For the following part, we describe the input graph given in Figure <ref>.
Throughout the manuscript, we index the vertices from left to right, and from bottom to top, in ascending order.

[xscale=0.8, yscale=0.3,
triangle/.style = regular polygon, regular polygon sides=3,
ltriangle/.style = regular polygon, regular polygon sides=3, rotate=90,
rtriangle/.style = regular polygon, regular polygon sides=3, rotate=270,
dtriangle/.style = regular polygon, regular polygon sides=3, rotate=180]

[draw=none] at (-0.7,-7) $P_L$;
[draw=none] at (10.7,-7) $P_R$;
[draw=none] at (-0.7,0) $P_\alpha$;
[draw=none] at (2.7,-6.5) $P_q$;
[draw=none] at (4.7,-6.5) $P_r$;
[draw=none] at (6.7,-6.5) $P_s$;
[draw=none] at (8.7,-6.5) $P_t$;

every node=[draw, shape=circle, minimum size=5pt,inner sep=0pt];

ıin 0,2,4,6,8,10 [shape=rectangle, fill=green!80!black, minimum size=4pt] (ı0) at (ı,0) ;

ıin 1,3,5,7,9	[shape=rectangle, fill=yellow!90!black, minimum size=4pt] (ı0) at (ı,0) ;

ıin 0,...,9

[very thick, color=yellow!90!black] (ı0)–(ȷ0);

ıin 2,4,6,8

ȷin -7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7

[fill=blue!90!black] (ıȷ) at (ı,ȷ) ;

ıin 2,4,6,8

ȷin -7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6

[very thick, color=blue] (ıȷ)–(ı)̨;

ıin 0,10

ȷin -7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7

[shape=rectangle,fill=blue!80!black, minimum size=4pt] (ıȷ) at (ı,ȷ) ;

ıin 0,10

ȷin -7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6

[very thick, color=blue!80!black] (ıȷ)–(ı)̨;

ıin -5.5,-3.5,-1.5,1.5,3.5,5.5

[ltriangle, fill=red] (-1ȷ) at (-0.7,ı) ;
[rtriangle, fill=red] (1ȷ) at (0.7,ı) ;

[ltriangle, fill=red] (9ȷ) at (9.3,ı) ;
[rtriangle, fill=red] (11ȷ) at (10.7,ı) ;

ıin 2,4,6,8

[triangle, fill=red] (ı9) at (ı,8.3) ;
[dtriangle, fill=red] (ı-9) at (ı,-8.3) ;

ıin 1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5

[shape=rectangle, fill=red, minimum size=4pt] (ȷ8) at (ı,7.5) ;
[shape=rectangle, fill=red, minimum size=4pt] (ȷ-8) at (ı,-7.5) ;

ıin 2,4,6,8

Skeleton of the input graph for $\Phi$. The consecutive induced paths, labeled as $P_q, P_r, P_s, P_t$, are to be embedded on the literal lines $\ell_q, \ell_r, \ell_s, \ell_t$ in Figure <ref> respectively. The vertices in the long induced paths $P_L$ and $P_R$ in <ref> (indicated by rectangles) must be embedded on the lines $\ell_L$ and $\ell_R$ given in <ref>. Similarly, the vertices in $P_\alpha$ (indicated by blue and green rectangles) must be embedded on the line $\ell_\alpha$ given in <ref>.

[ultra thick] (-2,8.5) – (22, 8.5);
[draw=none] at (-3,8.5) $\ell_\Delta$;
[ultra thick] (-2,0) – (22,0);
[draw=none] at (-3,0) $\ell_\alpha$;
[ultra thick] (-2,-8.5) – (22, -8.5);
[draw=none] at (-3,-8.5) $\ell_\nabla$;

[ultra thick] (0,-10) – (0, 10);
[draw=none] at (0,-11) $\ell_L$;
[ultra thick] (20,-10) – (20, 10);
[draw=none] at (20,-11) $\ell_R$;

[draw=none] at (-3,2.5) $\ell_A$;
[draw=none] at (-3,4.5) $\ell_B$;
[draw=none] at (-3,6.5) $\ell_C$;
[draw=none] at (-3,-2.5) $\ell_A'$;
[draw=none] at (-3,-4.5) $\ell_B'$;
[draw=none] at (-3,-6.5) $\ell_C'$;
[draw=none] at (4,-11) $\ell_q$;
[draw=none] at (8,-11) $\ell_r$;
[draw=none] at (12,-11) $\ell_s$;
[draw=none] at (16,-11) $\ell_t$;

ıin 1,2,3

(-2,2*ı+0.5) – (22,2*ı+0.5);
(-2,2*-ı-0.5) – (22,2*-ı-0.5);

ıin 1,2,3,4

(4*ı,-10) – (4*ı, 10);

The line set of the configuration for a Monotone NAE3SAT formula $\Phi$ with $4$ literals ($q,r,s,t$) and $3$ clauses ($A,B,C$).

Three essential components of the input graph is the following induced paths
$P_\alpha = (\alpha_1, \alpha_2, \dots, \alpha_{11})$,
$P_L = (L_1, L_2, \dots, L_{15})$,
and $P_R = (R_1, R_2, \dots, R_{15})$.
The length of $P_\alpha$ is $2m+3$ for $m$ literals. In our case, $(2\times 4) +3 = 11$.
The lengths of $P_L$ and $P_R$ are the same, equal to $3 + 4k$ for $k$ clauses. In our case, $3 + (4\times 3) = 15$.

The middle vertices of $P_L$ and $P_R$ are the end vertices of $P_\alpha$.
That is, $\alpha_1 = L_8$, and $\alpha_{11} = R_8$.
The paths $P_L$ and $P_R$ define the left and the right boundary for our gadget, respectively.

For $i  = q,r,s,t$, there is an induced path $P_i = (i_1, \dots, i_{15})$ for each literal, with 15 vertices.
In general, we denote those paths by $P^1, P^2, \dots, P^m$ for $m$ literals.
The vertices of these paths are denoted by blue circles in the Figure <ref>, they are mutually disjoint, but each of them shares one vertex with $P_\alpha$.
The shared vertices are precisely the middle vertices, those are indicated by green rectangle vertices in the figure.
That is, $\alpha_3 = q_8$, $\alpha_5 = r_8$, $\alpha_7 = s_8$, and $\alpha_9 = t_8$.
Moreover, $i_1$ is a vertex of an induced 4-cycle, and $i_{15}$ is a vertex of another induced 4-cycle for $i = q,r,s,t$.
The three vertices in a 4-cycle, except the one in one of the induced paths, are indicated by the red color in the figure.
Precisely two of them, that are adjacent to a blue vertex (either $i_1$ or $i_{15}$) are indicated by squares, and the remaining is indicated by a triangle.

[draw=none] at (-3.5,0) $\ell_\alpha$;

[draw=none] at (0,-12) $\ell_L$;
[draw=none] at (19,-12) $\ell_R$;

[draw=none] at (3.8,-12) $\ell_p$;
[draw=none] at (7.6,-12) $\ell_q$;
[draw=none] at (11.4,-12) $\ell_r$;
[draw=none] at (15.2,-12) $\ell_s$;

[draw=none] at (-3.5,-9) $\ell_\nabla$;
[draw=none] at (-3.5,-7.05) $\ell'_C$;
[draw=none] at (-3.5,-4.85) $\ell'_B$;
[draw=none] at (-3.5,-2.65) $\ell'_A$;
[draw=none] at (-3.5,2.65) $\ell_A$;
[draw=none] at (-3.5,4.85) $\ell_B$;
[draw=none] at (-3.5,7.05) $\ell_C$;
[draw=none] at (-3.5,9) $\ell_\Delta$;

every node=[draw, fill=black, shape=circle, minimum size=2pt,inner sep=0pt];

[thick] (-3,0)–(22,0);

ıin 0,1.9,3.8,5.7,7.6,9.5,11.4,13.3,15.2,17.1,19

at (ı,0) ;
(ı,0) circle[radius=1];

ıin 3.8,7.6,11.4,15.2

ȷin -7.6,-6.5,-5.4,-4.3,-3.2,-2.1,-1.05,1.05,2.1,3.3, 4.4,5.5, 6.6,7.7

at (ı,ȷ) ;
(ı,ȷ) circle[radius=1];

ıin 0,19

ȷin -7.6,-6.5,-5.4,-4.3,-3.2,-1.9,1.9,3.3, 4.4,5.5, 6.6,7.7

at (ı,ȷ) ;
(ı,ȷ) circle[radius=1];

ıin 0,3.8,7.6,11.4,15.2,19

ıin -7.05,-4.85,-2.65,2.65,4.85,7.05

at (1.5,ı) ;
at (-1.5,ı) ;
at (17.5,ı) ;
at (20.5,ı) ;
(1.5,ı) circle[radius=1];
(-1.5,ı) circle[radius=1];
(17.5,ı) circle[radius=1];
(20.5,ı) circle[radius=1];

[thick] (-3,9)–(22,9);
[thick] (-3,-9)–(22,-9);

ıin 0,2.32, 4.38, 6.43, 8.48, 10.53, 12.58, 14.63, 16.68,19

at (ı,9) ;
(ı,9) circle[radius=1];
at (ı,-9) ;
(ı,-9) circle[radius=1];

ıin 3.8,7.6,11.4,15.2

ȷin -9.8,9.8

at (ı,ȷ) ;
(ı,ȷ) circle[radius=1];

Realization of the graph given in <ref> onto the lines given in <ref>.

Starting from the second edge of $P_L$ (respectively $P_R$), every second edge is a chord of a 4-cycle ($C_4$).
Throughout the paper, we refer to such 4-cycles with a chord as a diamond.
Two vertices of these diamonds are of $P_L$ (respectively $P_R$), and remaining two are denoted by red triangles in Figure <ref>.

Remember that the problem takes two inputs: a graph, and a set of lines determined by their equations (or rather by two sets of rational numbers, since every line is parallel to either $x$- or $y$- axis).
For a Monotone NAE3SAT formula with $3$ clauses and $4$ literals, we have described the input graph above.
Now, let us discuss the input lines of our gadget.
The input graph is given in Figure <ref>, and the corresponding lines are given in Figure <ref>.
We claim that the given graph can be embedded onto the given lines with $\varepsilon$ flexibility, and the resulting realization looks like the set of unit disks given in Figure <ref>.

In order to force such embedding, we adjust the Euclidean distance between each pair of parallel lines carefully.
We start by defining the horizontal line $\ell_\alpha$.
This line is the axis of horizontal symmetry for our line configuration.
Thus, it is safe to assume that $\ell_\alpha$ is the $x$-axis.
On the positive side of the $y$-axis, for each clause $A$, $B$, and $C$, there is a straight line parallel to $\ell_\alpha$, and another horizontal line acting as the top boundary of the configuration.
These lines are denoted by $\ell_A, \ell_B$, $\ell_C$, and $\ell_\Delta$, and their equations are $y = a$, $y = b$, $y = c$, and $y = \Delta$, respectively, where $a < b < c < \Delta$.
For every pair of consecutive horizontal lines, the Euclidean distance between them is precisely $2.01$ units.
That is, $a = 2.01$, $b = 4.02$ and $c = 6.03$, and $\Delta = 8.04$.
Note that $2.01$ is sufficiently small for the case where there are three clauses.
In general, this value is $(2 + \varepsilon)$ where $\varepsilon \leq 1/4k$.
For every horizontal line described above, there is another horizontal line symmetric to it about the $x$-axis.
These lines are $\ell'_A, \ell'_B, \ell'_C$, and $\ell_\nabla$ (see Figure <ref>).

The leftmost vertical line is $\ell_L$, which is the left boundary of our configuration.
We can safely assume that $\ell_L$ is the $y$-axis for the sake of simplicity.
For each literal $q$, $r$, $s$ and $t$, there exists a vertical line parallel to $\ell_L$, and another vertical line that defines the right boundary of our configuration.
These lines are denoted by $\ell_q, \ell_r$, $\ell_s$, $\ell_t$, and $\ell_R$, and their equations are $x = q$, $x = r$, $x = s$, $x = t$ and $x = R$, respectively, where $q < r < s < t < R$.
The Euclidean distance between each pair of consecutive vertical lines is precisely $3.8$ units.
That is $q = 3.8$, $r = 7.6$, $s = 11.4$, $t = 15.2$, and $R = 19$.

Up to this point, we have described the input graph, and the input lines for a given Monotone NAE3SAT formula with 3 clauses and 4 literals.
In general, for a given Monotone NAE3SAT formula $\Phi$ with $k$ clauses $C_1, C_2, \dots, C_k$, and $m$ literals $x_1, x_2, \dots, x_m$, the $\APUD(2k+1, m+2)$ instance has the components that are listed in Figure <ref>.

* An induced path $P_\alpha = (\alpha_1, \alpha_2, \dots, \alpha_{2m+3})$ with $2m+3$ vertices.

* $m$ induced paths $P^1 = (P^1_1, P^1_2, \dots, P^1_{4k+3})$, $\dots$, $P^m = (P^m_1, P^m_2, \dots, P^m_{4k+3})$, each with $4k+3$ vertices, where $\alpha_3 = P^1_{2k+2}$, $\alpha_5 = P^2_{2k+2}$, $\dots$, $\alpha_{2k+1} = P^m_{2k+2}$, and induced 4-cycles containing the first and the last vertices of each of these paths.

* Two induced paths $P_L = (L_1, \dots, L_{4k+3})$ and $P_R = (R_1, \dots, R_{4k+3})$, each with $4k+3$ vertices, where the edges
$L_2L_3$, $L_4L_5$, $\dots$, $L_{2k}L_{2k+1}$, $L_{2k+3}L_{2k+4}$, $\dots$, $L_{4k+1}L_{4k+2}$, and

$R_2R_3$, $R_4R_5$, $\dots$, $R_{2k}R_{2k+1}$, $R_{2k+3}R_{2k+4}$, $\dots$, $R_{4k+1}R_{4k+2}$ are chords of disjoint 4-cycles.

* $2k+3$ horizontal lines $\ell_\nabla, \ell'^C_k, \ell'^C_{k-1}, \dots, \ell_\alpha, \ell^C_1, \ell^C_2, \dots, \ell^C_k, \ell_\Delta$, with equations

$\ell_\nabla: y= -(2+\varepsilon)(k+1)$

$\ell_\Delta: -\ell_\nabla$

$\ell_\alpha: y = 0$

$\ell'^C_{i} = -(2+\varepsilon)i$,

and $\ell^C_{i} = (2+\varepsilon)i$ for $i = 1,2,\dots,k$  and for $\varepsilon \leq 1/4k$.

* $m+2$ vertical lines $\ell_L, \ell^x_1, \ell^x_2, \dots, \ell^x_m, \ell_R$, with equations $\ell_L: x = 0$,

$\ell_R: x = 3.8(m+1)$,

and $\ell^x_i: 3.8i$ for $i = 1,2,\dots,m$.

The straight line configuration for the gadget that corresponds to a NAE3SAT formula with $k$ clauses and $m$ lines.

In total, for the given formula $\Phi$ with $k$ clauses and $m$ literals, our gadget is an instance of $\APUD(2k+3,m+2)$.

Now, let us show that the given graph has a unique embedding onto the given lines, up to $\varepsilon$ flexibility.

The vertices indicated by rectangles in Figure <ref> can only be embedded on the bold lines in Figure <ref>.

We prove this proposition by giving a series of lemmas.

Let us start by discussing the embedding of $P_L$ onto $\ell_L$ (and respectively $P_R$ onto $\ell_R$).
We give the following two trivial lemmas as preliminaries for the proof of our claim.

Consider two disks $A$ and $B$, centered on $(a,0)$ and $(b,0)$ with $0<|a|<|b|$.
Another disk, $C$ that is centered on $(0,c)$ cannot intersect $B$ without intersecting $A$.

Consider the triangle whose corners are $(a,0)$, $(b,0)$, and $(0,c)$.
If $|a|<|b|$, then $\sqrt{a^2+c^2} < \sqrt{b^2+c^2}$ holds.
For $C$ to intersect $B$, $\sqrt{b^2+c^2} \leq 2$ must hold.
However, since $|a| < |b|$, if $\sqrt{b^2+c^2} \leq 2$ holds, then $\sqrt{a^2+c^2} \leq 2$ also holds.
Thus, $C$ intersects $B$ if, and only if $C$ intersects $A$.

An induced 4-star ($K_{1,4}$) can be realized as a unit disk graph on two perpendicular lines, but not on two parallel lines.

First part of the proof is trivial.
Consider the $x=0$ and $y=0$ lines as two perpendicular lines.
Four unit disks centered on $(0,-(2-\varepsilon)$, $((2-\varepsilon),0)$, $(0, (2-\varepsilon)$, and $(-(2-\varepsilon),0)$ where $0 < \varepsilon \ll 1$ form an induced 4-star ($K_{1,4}$).

Now, let us show that an induced 4-star cannot be realized as unit disks on two parallel lines.
The disks that correspond to the vertices of an induced claw ($K_{1,3}$) can be embedded on two parallel lines if the centers of three disks are collinear.
Suppose that four disks, $A$, $B$, $C$, and $U$ form an induced claw, where $U$ is the central vertex, and $A,B,C$ are the rays.
Without loss of generality, suppose that $A$, $U$, and $C$ are centered on $(a,0)$, $(0,0)$ and $(c,0)$, respectively.
Thus, $B$ must be on the second parallel line, say $y=k$.
To complete a 4-star, we need one more disk, $D$, centered on either $y=0$ or $y=k$, such that $D$ intersects $U$, but none of $A$, $B$, and $C$

Clearly, $D$ cannot be on $y=0$ line because $U$ is enclosed by $A$ and $C$ from both sides.
So, suppose that $D$ is centered on $(d,k)$.
In this case, we show that no such $k$ exists by contradiction.

Place two more disks, $B'$ and $D'$, centered on $(-b,k)$ and $(-d,k)$, respectively.
If $B$ and $D$ do not intersect, then $B'$ and $D'$ also do not intersect.
Moreover, since $A$ does not intersect with $B$, $A$ also does not intersect with $B'$.
Symmetrically, $C$, $D$, $C'$, and $D'$ have no pairwise intersections.

The described configuration is a $K_{1,6}$ with disks $U;A,B,C,D,B',D'$ which cannot be realized as a unit disk graph.
Therefore, we have a contradiction.

If an induced 4-cycle ($C_4$) can be realized as a unit disk graph on two perpendicular lines that intersect at $\omega$, then the following hold:

* A pair of non-intersecting disks must be on the same line, but at the different sides of $\omega$.

* The the Euclidean distance between $\omega$ and any disk center is strictly greater than $2 - \sqrt{3}$ and strictly less than $\sqrt{3}$.

Without loss of generality, let two perpendicular lines be the $x$- and $y$-axes, and thus let $\omega$ be $(0,0)$.
Denote the vertices of 4-cycle by $a,b,c,d$ in clockwise order.
That is, the edges $ab$, $bc$, $cd$, and $ad$ exist.
Denote the disks which correspond to these vertices by $A$, $B$, $C$, and $D$.

Suppose that two non-intersecting disks, $A$ and $C$ are centered at $(a,0)$ and $(c,0)$, respectively where $0 \leq a \leq c$.
Since $c-a > 2$ and $a > 0$, then $c > 2$, which means that any disk which intersects $C$ cannot be on $y$-axis.
However, both $B$ and $D$ cannot be on $x$-axis because then we have a unit interval graph, in which an induced 4-cycle cannot appear.
Thus, if $ac < 0$ must hold and symmetrically, $bd <0$ must also hold.
Therefore (i) holds.

Up to symmetry, assume that $A$, $B$, $C$ and $D$ are centered at $(a,0)$, $(0,b)$, $(c,0)$ and $(0,d)$, respectively, where $a,c < 0$ and $b,d > 0$.
Then, the following equations hold:

\begin{align}
|a - c| > 2\\
|b - d| > 2\\
\sqrt{a^2+b^2} \leq 2\\
\sqrt{b^2+c^2} \leq 2\\
\sqrt{c^2+d^2} \leq 2\\
\sqrt{d^2+a^2} \leq 2
\end{align}

Let us minimize the value of $|d|$, which is simply the Euclidean distance between the intersection point of two perpendicular lines and the center of $D$.
Due to (2), $|d|$ is minimized when $|b|$ is maximized.
Due to (3) and (4), the maximum value of $|b|$ is achieved when $|a|-|c|$ is minimum.
Due to (1), $|a| - |c|$ is minimum when $|a| = |c| = 1 + 2\sqrt{\varepsilon}$ where $\varepsilon$ is sufficiently small.
In order to maximize the value of $|b|$, we must assign $a = -(1 + \sqrt{\varepsilon})$, and $c = 1 + \sqrt{\varepsilon}$.
Then, the value of $b$ is $\sqrt{3 - \varepsilon}$ which is strictly less than $\sqrt{3}$, and due to (2), the value of $d$ is strictly greater than $2 - \sqrt{3}$.
Since we maximized the value of $b$ and minimized the value of $d$, we can now conclude that (ii) holds.

Now, with the help of Lemmas <ref> and <ref>, we state the following lemmas, and finish the proof of Proposition <ref>.

The induced paths $P_L$, $P_R$ and $P_\alpha$ in the input graph (Figure <ref>) can only be embedded onto $\ell_L$, $\ell_R$, and $\ell_\alpha$, respectively (Figure <ref>).

Assume that $P_L = (L_1, \dots, L_{4k+3})$ is realized on a single line, say $d$.
Denote the disks $\mathcal{D}_L^1, \dots \mathcal{D}_L^{4k+3}$ that correspond to these vertices, respectively.
Denote the disks $\mathcal{D}_\alpha^1, \dots, \mathcal{D}_\alpha^{2m+3}$ that correspond to the vertices ($\alpha_1, \dots, \alpha_{2m+3}$) of $P_\alpha$.

Consider the diamond $u,v,L_{4k-1}, L_{4k}$, where $u$ and $v$ are indicated by red triangles in Figure <ref>.
Neither $U$ nor $V$ intersect any disk that corresponds to a vertex of $P_L$.
Therefore, neither of them can be embedded onto $d$.
Similarly, if they are embedded onto some other line perpendicular to $d$, then they intersect either $\mathcal{D}_L^{4k-2}$ or $\mathcal{D}_L^{4k+1}$ to intersect $\mathcal{D}_L^{4k-1}$ and $\mathcal{D}_L^{4k}$.
Thus, every such pair of disks must be embedded in a way such that their centers lie onto the same line that intersects $d$, and at the different sides of $d$.
This property also holds for the diamond that includes the vertices $L_{4k+1}$ and $L_{4k+2}$, as there is one extra vertex $L_{4k+3}$ at the end of $P_L$.

There are $2k$ disjoint diamonds in which $4k$ vertices of $P_L$ are included.
Each of these diamonds must be embedded around the intersection of two perpendicular lines.
In addition, there is one vertex that $P_L$ and $P_\alpha$ have in common ($\alpha_1 = L_{2k+2}$).
Since $P_\alpha$ is an induced path, each disk $\mathcal{D}_\alpha^i$ such that $1 \leq i \leq 2m+3$ cannot be centered on $d$.
Thus, the center of the disk $\mathcal{D}_L^{2k+2} = \mathcal{D}_\alpha^1$, must be the closest center to some line $f$ on which $\mathcal{D}_\alpha^2$ is centered.
Otherwise, due to Lemma <ref>, $\mathcal{D}_\alpha^2$ intersects with a closer to $f$.

Therefore, to embed $P_L$, there must be a straight line, and precisely $2k+1$ parallel lines that are perpendicular to this line.
Similarly, $P_R$ also requires $2k+1$ intersection points to be realized.
Thus, both $P_L$ and $P_R$ must be realized on two distinct vertical lines.

Now recall Lemma <ref>.
Note that each one of $\alpha_3, \alpha_5, \dots \alpha_{2m+1}$ is the central vertex of some 4-star, and thus must be embedded near the intersection of two perpendicular lines.
Considering that $P_L$ and $P_R$ are realized on two vertical lines, we need $m+2$ intersection points to realize $P_\alpha$ as unit disks.
Since $\alpha_1 = L_{2k+2}$ and $\alpha_{2m+3} = R_{2k+2}$, the remaining four intersections for 4-stars are the intersections between $\ell_alpha$ and each of $\ell_q, \ell_r, \ell_s, \ell_t$.
It is now trivial to see that our initial assumption of $P_L$ being realized on a single line always holds, since if $P_L$ is realized on more than one straight lines, then $P_\alpha$ cannot be realized due to the number of intersections.
Of course, one also needs to take into account the other induced paths, $P^1, \dots, P^m$ to verify this statement.

Therefore, $P_L$, $P_R$ and $P_\alpha$ can only be embedded onto $\ell_L$, $\ell_R$, and $\ell_\alpha$, respectively.

A pair of non-intersecting disks that are included in an induced 4-cycle, but not included in any of $P^1, P^2, \dots, P^m$, must lie on either $\ell_\Delta$ or $\ell_\nabla$ (red rectangles in Figure <ref>).

In any 4-cycle, two of the disks must be centered on the same line, and the remaining two must be centered a line which is perpendicular to the line on which the first two are centered.
Moreover, the centers must lie at four different directions from the intersection point.

Therefore, a non-intersecting pair of disks from each induced 4-cycle must be centered on $\ell_\Delta$ and $\ell_\nabla$.
The vertices to which those pairs of disks correspond are indicated by red rectangles in Figure <ref>.

The following three propositions altogether show that for a given instance of NAE3SAT with $k$ clauses and $m$ literals, the corresponding graph has a unique embedding up to $\varepsilon$ flexibility onto the corresponding line configuration.
Proposition <ref> shows that the long induced paths $P^1, \dots, P^m$ in the input graph must be embedded onto the vertical lines.
Proposition <ref> shows that on a vertical line, the disks which correspond to these paths must be embedded between the top line $\ell_\Delta$ and the bottom line $\ell_\nabla$ in the line configuration.

The induced paths
$P^1 = (P^1_1, \dots, P^1_{4k+3})$,
$P^2 = (P^2_1, \dots, P^2_{4k+3})$, $\dots$,
$P^m = (P^m_1, \dots, P^m_{4k+3})$ in the input graph can only be embedded onto $\ell^x_1$, $\ell^x_2$, $\dots$ $\ell^x_m$, respectively.

Due to Lemma <ref>, we know that $P_\alpha$ is realized on $\ell_\alpha$.
Also recall that for $1 \leq i \leq k$; $\alpha_{2i+1} = P^i_{2k+2}$ holds.
Since every $P^i_{2k+2}$ is a central vertex of some 4-star, as well as the middle vertex of the path $P^i$, the induced path $P^1, P^2, \dots, P^m$ must be realized on $\ell^x_1, \ell^x_2, dots, \ell^x_m$, respectively.

Before stating the next proposition, let us remind that a 4-cycle is an induced subgraph in a unit interval graph and hence can be realized as a unit disk intersection graph onto two distinct straight lines.
In our case, two lines are either parallel or perpendicular.
Since every pair of parallel lines has the Euclidean distance strictly greater than $2$ units in between, it is clear that we have to embed an induced 4-cycle onto two perpendicular lines.
Moreover, considering the clockwise order $a,b,c,d$ on an induced 4-cycle, remember that by Lemma <ref>, the vertex pairs $a,c$ must be on one of the perpendicular lines, and $b,d$ must be on the other line.

The center of each disk that correspond to a vertex of the induced paths $P^1, \dots, P^m$ must be between $\ell_\Delta$ and $\ell_\nabla$.

By Lemma <ref>, we already know that the disk which corresponds to the middle vertex $P^i_{2k+2}$ of some path $P^i$ must be on the line $\ell_\alpha$.

Consider the $2k+2$ disks which correspond to the vertices $P^i_{2k+2}, \dots, P^i_{4k+3}$ for some $i$.
Let us denote these disks by $D_1, \dots, D_{2k+2}$.
Note that $P^i_{2k+2}$ is the central vertex of a 4-star, and $P^i_{4k+3}$ is a vertex of a 4-cycle.
That is, the disks which correspond to$P^i_{2k+3}$
These disks yield an induced path, and thus the Euclidean distance between the centers of the first disk and the last disk on the path must be strictly greater than $2k$ units.
Thus, the disk which corresponds to the vertex $P^i_{4k+3}$ must be embedded above the horizontal line  $\ell^C_{k-1} : y = (2+\varepsilon)(k-1)$ which is strictly less than $2k$ for a sufficiently small value of $\varepsilon$.

Let us denote the disk which corresponds to the vertex $P^i_{4k+3}$ by $\mathcal{D}$, and $y$-coordinate of the center of that disk by $\psi$.
By Lemma <ref>, in order to form an induced 4-cycle, $\mathcal{D}$ must be below the horizontal line $\ell^C_k : y = (2+\varepsilon)k$, and the Euclidean distance between the center of $\mathcal{D}$ and $\ell^C_k$ must be greater than $2- \sqrt{3}$.

\begin{align*}
\psi & > 2k\\
(2+\varepsilon)k - \psi & > 2 - \sqrt{3}
\end{align*}

Which can be rewritten as

\begin{align*}
2k &< \psi < (2+\varepsilon)k - 2 + \sqrt{3}\\
2k &< (2+\varepsilon)k - 2 + \sqrt{3}\\
2 - \sqrt{3} &< \varepsilon k
\end{align*}

which is a contradiction for $\varepsilon \leq 1/4k$.

For the given input graph that corresponds to a NAE3SAT formula with $k$ clauses and $m$ literals, the following hold:

* A pair of non-intersecting disks that are included in an induced 4-cycle, but not included in any of $P^1, P^2, \dots, P^n$, must lie on either $\ell_\Delta$ or $\ell_\nabla$.

* The induced paths
$P^1 = (P^1_1, \dots, P^1_{4k+3})$,
$P^2 = (P^2_1, \dots, P^2_{4k+3})$, $\dots$,
$P^n = (P^m_1, \dots, P^m_{4k+3})$ in the input graph can only be embedded onto $\ell^x_1$, $\ell^x_2$, $\dots$ $\ell^x_m$, respectively.

* The center of each disk that correspond to a vertex of those induced paths must be between $\ell_\Delta$ and $\ell_\nabla$.

Directly follows from Lemma <ref>, Lemma <ref> and Lemma <ref>.

With the Lemma <ref> and Proposition <ref>, we have shown that the vertices denoted by rectangles in Figure <ref> must be embedded onto the bold lines in Figure <ref>, which was stated in Proposition <ref>.
For a quick visual verification of these lemmas, we refer the reader to the Figures <ref> and <ref> with values $k=3$ and $m=4$.

[xscale=0.45, yscale=0.3,
triangle/.style = regular polygon, regular polygon sides=3,
ltriangle/.style = regular polygon, regular polygon sides=3, rotate=90,
rtriangle/.style = regular polygon, regular polygon sides=3, rotate=270,
dtriangle/.style = regular polygon, regular polygon sides=3, rotate=180]

[draw=none] at (-0.7,-7) $P_L$;
[draw=none] at (10.7,-7) $P_R$;
[draw=none] at (-0.7,0) $P_\alpha$;
[draw=none] at (2.7,-6.5) $P_q$;
[draw=none] at (4.7,-6.5) $P_r$;
[draw=none] at (6.7,-6.5) $P_s$;
[draw=none] at (8.7,-6.5) $P_t$;

every node=[draw, shape=circle, minimum size=5pt,inner sep=0pt];

ıin 0,2,4,6,8,10 [shape=rectangle, fill=green!80!black, minimum size=4pt] (ı0) at (ı,0) ;

ıin 1,3,5,7,9	[shape=rectangle, fill=yellow!90!black, minimum size=4pt] (ı0) at (ı,0) ;

ıin 0,...,9

[very thick, color=yellow!90!black] (ı0)–(ȷ0);

ıin 2,4,6,8

ȷin -7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7

[fill=blue!90!black] (ıȷ) at (ı,ȷ) ;

ıin 2,4,6,8

ȷin -7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6

[very thick, color=blue] (ıȷ)–(ı)̨;

ıin 0,10

ȷin -7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7

[shape=rectangle,fill=blue!80!black, minimum size=4pt] (ıȷ) at (ı,ȷ) ;

ıin 0,10

ȷin -7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6

[very thick, color=blue!80!black] (ıȷ)–(ı)̨;

ıin -5.5,-3.5,-1.5,1.5,3.5,5.5

[ltriangle, fill=red] (-1ȷ) at (-0.7,ı) ;
[rtriangle, fill=red] (1ȷ) at (0.7,ı) ;

[ltriangle, fill=red] (9ȷ) at (9.3,ı) ;
[rtriangle, fill=red] (11ȷ) at (10.7,ı) ;

ıin 2,4,6,8

[triangle, fill=red] (ı9) at (ı,8.3) ;
[dtriangle, fill=red] (ı-9) at (ı,-8.3) ;

ıin 1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5

[shape=rectangle, fill=red, minimum size=4pt] (ȷ8) at (ı,7.5) ;
[shape=rectangle, fill=red, minimum size=4pt] (ȷ-8) at (ı,-7.5) ;

ıin 2,4,6,8

ıin -5.5,-3.5,-1.5

in 3,5,7

[shape=diamond,fill=orange!90!black] (ȷ) at (,ı) ;
[very thick, color=orange!90!black] (ȷ)–(ȷ);
[very thick, color=orange!90!black] (ȷ)–();

[shape=diamond,fill=orange!90!black] (9)̨ at (9,)̨ ;
[very thick, color=orange!90!black] (9)̨–(8)̨;
[very thick, color=orange!90!black] (9)̨–(8)̨;
[very thick, color=orange!90!black] (9)̨–(8ł);

[shape=diamond, fill=orange!90!black] (52) at (5, 1.5) ;
[very thick, color=orange!90!black] (52)–(41);
[very thick, color=orange!90!black] (52)–(42);

[shape=diamond,fill=orange!90!black] (74) at (7, 3.5) ;
[very thick, color=orange!90!black] (74)–(63);
[very thick, color=orange!90!black] (74)–(64);

[shape=diamond,fill=orange!90!black] (75) at (7,5.5) ;
[very thick, color=orange!90!black] (75)–(85);
[very thick, color=orange!90!black] (75)–(86);

[xscale=0.45, yscale=0.3,
triangle/.style = regular polygon, regular polygon sides=3,
ltriangle/.style = regular polygon, regular polygon sides=3, rotate=90,
rtriangle/.style = regular polygon, regular polygon sides=3, rotate=270,
dtriangle/.style = regular polygon, regular polygon sides=3, rotate=180]

[draw=none] at (-0.7,-7) $P_L$;
[draw=none] at (10.7,-7) $P_R$;
[draw=none] at (-0.7,0) $P_\alpha$;
[draw=none] at (2.7,-6.5) $P_q$;
[draw=none] at (4.7,-6.5) $P_r$;
[draw=none] at (6.7,-6.5) $P_s$;
[draw=none] at (8.7,-6.5) $P_t$;

every node=[draw, shape=circle, minimum size=5pt,inner sep=0pt];

ıin 0,2,4,6,8,10 [shape=rectangle, fill=green!80!black, minimum size=4pt] (ı0) at (ı,0) ;

ıin 1,3,5,7,9	[shape=rectangle, fill=yellow!90!black, minimum size=4pt] (ı0) at (ı,0) ;

ıin 0,...,9

[very thick, color=yellow!90!black] (ı0)–(ȷ0);

ıin 2,4,6,8

ȷin -7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7

[fill=blue!90!black] (ıȷ) at (ı,ȷ) ;

ıin 2,4,6,8

ȷin -7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6

[very thick, color=blue] (ıȷ)–(ı)̨;

ıin 0,10

ȷin -7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7

[shape=rectangle,fill=blue!80!black, minimum size=4pt] (ıȷ) at (ı,ȷ) ;

ıin 0,10

ȷin -7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6

[very thick, color=blue!80!black] (ıȷ)–(ı)̨;

ıin -5.5,-3.5,-1.5,1.5,3.5,5.5

[ltriangle, fill=red] (-1ȷ) at (-0.7,ı) ;
[rtriangle, fill=red] (1ȷ) at (0.7,ı) ;

[ltriangle, fill=red] (9ȷ) at (9.3,ı) ;
[rtriangle, fill=red] (11ȷ) at (10.7,ı) ;

ıin 2,4,6,8

[triangle, fill=red] (ı9) at (ı,8.3) ;
[dtriangle, fill=red] (ı-9) at (ı,-8.3) ;

ıin 1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5

[shape=rectangle, fill=red, minimum size=4pt] (ȷ8) at (ı,7.5) ;
[shape=rectangle, fill=red, minimum size=4pt] (ȷ-8) at (ı,-7.5) ;

ıin 2,4,6,8

ıin -5.5,-3.5,-1.5

in 3

[shape=diamond,fill=orange!90!black] (ȷ) at (,ı) ;
[very thick, color=orange!90!black] (ȷ)–(ȷ);
[very thick, color=orange!90!black] (ȷ)–();

[shape=diamond,fill=orange!90!black] (9)̨ at (7,ı) ;
[very thick, color=orange!90!black] (9)̨–(8)̨;
[very thick, color=orange!90!black] (9)̨–(8)̨;
[very thick, color=orange!90!black] (9)̨–(8ł);

ıin 5.5,3.5,1.5

in 3,5

[shape=diamond,fill=orange!90!black] (ȷ) at (,ı) ;
[very thick, color=orange!90!black] (ȷ)–(ȷ);
[very thick, color=orange!90!black] (ȷ)–();

[shape=diamond, fill=orange!90!black] (5-2) at (5, -1.5) ;
[very thick, color=orange!90!black] (5-2)–(4-1);
[very thick, color=orange!90!black] (5-2)–(4-2);

[shape=diamond,fill=orange!90!black] (7-4) at (5, -3.5) ;
[very thick, color=orange!90!black] (7-4)–(6-3);
[very thick, color=orange!90!black] (7-4)–(6-4);

[shape=diamond,fill=orange!90!black] (75) at (7,5.5) ;
[very thick, color=orange!90!black] (75)–(85);
[very thick, color=orange!90!black] (75)–(86);

[draw=none] at (-3.5,0) $\ell_\alpha$;

[draw=none] at (0,-12) $\ell_L$;
[draw=none] at (19,-12) $\ell_R$;

[draw=none] at (3.8,-12) $\ell_q$;
[draw=none] at (7.6,-12) $\ell_r$;
[draw=none] at (11.4,-12) $\ell_s$;
[draw=none] at (15.2,-12) $\ell_t$;

[draw=none] at (-3.5,-9) $\ell_\nabla$;
[draw=none] at (-3.5,-7.05) $\ell'_C$;
[draw=none] at (-3.5,-4.85) $\ell'_B$;
[draw=none] at (-3.5,-2.65) $\ell'_A$;
[draw=none] at (-3.5,2.65) $\ell_A$;
[draw=none] at (-3.5,4.85) $\ell_B$;
[draw=none] at (-3.5,7.05) $\ell_C$;
[draw=none] at (-3.5,9) $\ell_\Delta$;

every node=[draw, fill=black, shape=circle, minimum size=2pt,inner sep=0pt];

[thick] (-3,0)–(22,0);

ıin 0,1.9,3.8,5.7,7.6,9.5,11.4,13.3,15.2,17.1,19

at (ı,0) ;
(ı,0) circle[radius=1];

ıin 3.8,7.6,11.4,15.2

ȷin -7.6,-6.5,-5.4,-4.3,-3.2,-2.1,-1.05,1.05,2.1,3.3, 4.4,5.5, 6.6,7.7

at (ı,ȷ) ;
(ı,ȷ) circle[radius=1];

ıin 0,19

ȷin -7.6,-6.5,-5.4,-4.3,-3.2,-1.9,1.9,3.3, 4.4,5.5, 6.6,7.7

at (ı,ȷ) ;
(ı,ȷ) circle[radius=1];

ıin 0,3.8,7.6,11.4,15.2,19

ıin -7.05,-4.85,-2.65,2.65,4.85,7.05

at (1.5,ı) ;
at (-1.5,ı) ;
at (17.5,ı) ;
at (20.5,ı) ;
(1.5,ı) circle[radius=1];
(-1.5,ı) circle[radius=1];
(17.5,ı) circle[radius=1];
(20.5,ı) circle[radius=1];

[thick] (-3,9.1)–(22,9.1);
[thick] (-3,-9.1)–(22,-9.1);

ıin 0,2.32, 4.38, 6.43, 8.48, 10.53, 12.58, 14.63, 16.68,19

at (ı,9.1) ;
(ı,9.1) circle[radius=1];
at (ı,-9.1) ;
(ı,-9.1) circle[radius=1];

ıin 3.8,7.6,11.4,15.2

ȷin -9.8,9.8

at (ı,ȷ) ;
(ı,ȷ) circle[radius=1];

ıin 2.65,4.85,7.05

at (6,ı) ;
(6,ı) circle[radius=1];
at (9.8,ı) ;
(9.8,ı) circle[radius=1];

ıin -2.65,-4.85,-7.05

at (5.3,ı) ;
(5.3,ı) circle[radius=1];
at (13.7,ı) ;
(13.7,ı) circle[radius=1];

at (13.7,7.05) ;
(13.7,7.05) circle[radius=1];

at (9.8,-4.85) ;
(9.8,-4.85) circle[radius=1];

at (9,-2.65) ;
(9,-2.65) circle[radius=1];

(a) The input graph for the Monotone NAE3SAT formula with $\Phi$ with literals $q,r,s,t$, and clauses $A,B,C$.
The formula is written as $\Phi = A \wedge B \wedge C$  where $A = (q \vee s \vee t)$, $B = (q \vee r \vee t)$, and $C =(q \vee r \vee s)$. The flag vertices, indicated by orange diamonds, are adjacent to the vertices that correspond to a clause on an induced path, if the literal does not appear in that clause.

(b) A truth assignment that satisfies the formula given in <ref>: $q = \textsc{true}$, $r = \textsc{false}$, $s = \textsc{false}$, and $t = \textsc{true}$.

(c) Realization of the graph given in <ref>.

Using the backbone we have described, we now show how to model the relationship between the clauses and the literals.
To make it easier to follow, we also refer to Figure <ref> in parentheses in the following description.

* Consider a sub-path $(P^i_{2k+3}, P^i_{2k+4}$, $\dots$, $P^i_{4k+3})$ of the induced path $P^i$. This part corresponds to the literal $x_i$ of the given Monotone NAE3SAT formula (corresponds to $(q_9, \dots, q_{15})$ of $P_q$ in our example).

* The edges $P^i_{2k+3}P^i_{2k+4}$, $P^i_{2k+5}P^i_{2k+6}$, $\dots$, $P^i_{4k+1}P^i_{4k+2}$ (correspond to $q_9q_{10}$, $q_{11}q_{12}$, and $q_{13}q_{14}$ in $P_q$ in our example) are used to model membership of $x_i$ in the clauses $C_1$, $C_2$, $\dots$, $C_k$ (correspond to the clauses $A$, $B$, and $C$ in our example), respectively.

* If $x_i$ appears in a clause $C_j$, then we do nothing for the edges correspond do those clauses.

* Otherwise, if $x_i$ does not appear in $C_j$, then we introduce a flag vertex in the graph, which is adjacent to $P^i_{2(k+j)+1}$ and $P^i_{2(k+j)+2}$.

* Due to the rigidity of the backbone (up to $\varepsilon$ flexibility), this flag vertex lies on $\ell^C_j$.
Similarly, in our example, if $q$ appears in $B$, then $q_{11}q_{12}$ stays as is, but otherwise, a flag vertex is introduced, adjacent to both $q_{11}$ and $q_{12}$.

* Every clause has 3 literals. Thus, on each horizontal line, 3 out of $m$ possible flag vertices will be missing.
That sums up to a total of $k(m-3)$ flag vertices for this part of the graph.

* For the remaining sub-path $(P^i_1,\dots,P^i_{2k+2})$ of $P^i$ (corresponds to $(q_1,\dots,q_8)$ of $P_q$ in our example), we introduce the flag vertices for the pairs $(P^i_2,P^i_3)$, $(P^i_4,P^i_5)$, $\dots$, $P^i_{2k}$, $P^i_{2k+1}$ (correspond to $(q_6,q_7)$ $(q_2,q_3)$, $(q_4,q_5)$, $(q_6,q_7)$ in our example).

* That is a total number of $km$ flag vertices for this part of the graph. In the whole graph, there are precisely $2km-3k$ flag vertices.

* Finally, let us note that the value of $\varepsilon$ does not require more than polynomially many digits with respect to the input size, where $(2+\epsilon)$ is the distance between two consecutive parallel lines.
We assume that $\varepsilon < 1/4k$ where $k$ is the number of clauses in the given NAE3SAT formula.
Since $k$ is a part of the input, multiplying it by $0.25$ will not result a number whose decimal representation requires exponentially many digits.

Realize that the embeddings on some vertical lines must be flipped upside-down to create space for the flag vertices.
This operation corresponds to the truth assignment of the literal that corresponds to that vertical line.
The configuration forces at least one literal to have a different truth assignment, because for a pair of symmetrical horizontal lines, say $\ell_A$ and $\ell'_A$, there must be at least one, and at most two missing flags for the disks to fit between $\ell_L$ and $\ell_R$.
Here, we conclude the proof of Theorem <ref>.

The input graph, a YES-instance, and the realization of the YES-instance of the Monotone NAE3SAT formula $\Phi = (q \vee s \vee t) \wedge (q \vee r \vee t) \wedge (q \vee r \vee s)$ is given in Figure <ref>.

Before moving onto the next section, we would like to state a trivial corollary which is a natural result derived from Theorem <ref>.
To the best of our knowledge, there are no results on unit disk graph recognition problem with the input restricted by the size of the largest cycle.
A slightly related result was studied by Fomin, Lokshtanov and Saurabh in 2012 [52], which considers the cycle-packing problem on disk graphs with no large cliques.

Given a graph $G = (V,E)$, deciding whether $G$ is a unit disk graph is an NP-hard problem when the size of the largest induced cycle in $G$ is of length $4$.

In the NP-hardness proof given in Section <ref>, the largest cycles in the input graph are diamonds, and induced 4-cycles.
The rest of the graph consists of long paths.
Since axes-parallel unit disk graph recognition is a more restricted version of unit disk graph recognition problem, the claim holds.

§ APUD(K,0) RECOGNITION IS NP-COMPLETE

In this section, we show that the recognition of axes-parallel unit disk graphs is NP-complete, when all the given lines are parallel to each other.
This version of the problem is referred to as $\APUD(k,0)$, as there are $k$ horizontal lines given as input, but no vertical lines.
We use the reduction given in Section <ref>.

$\APUD(k,0)$ recognition is NP-hard.

Consider the realization given in Figure <ref>.
Notice that the length of the paths $P^1, P^2, \dots, P^m$ ($P_q, P_r, P_s, P_t$ in our example), and thus the number of disks on vertical lines is equal.
Lemma <ref> shows that the induced paths can only be realized by unit disks that are centered between $\ell_\nabla$ and $\ell_\Delta$.
Therefore, for the disks that correspond to the vertices on these paths, we do not need any vertical line.
Instead, we use triplets of parallel horizontal lines to simulate a vertical line.
For a horizontal line  $\ell^C_i$ in the line configuration we use in Secion <ref>, we add two horizontal lines, namely $\ell^{Ca}_i$ and $\ell^{Cb}_i$, where $\ell^{Ca}_i$ is above $\ell$, and $\ell^{Cb}_i$ is below $\ell$ both of which are symmetrically with respect to $\ell$.
The Euclidean distance between each $\ell_a$ and $\ell_b$ is $1 + \varepsilon$ where $\varepsilon$ is a sufficiently small value.
The disks which correspond to the long induced paths $P^1, \dots, P^m$ are placed on the extra two parallel lines, and thus the whole configuration is realized as described in Section <ref>.

As a result, for a given instance $\Phi$ of Monotone NAE3SAT formula with $k$ clauses and $m$ literals; we have an instance $\Psi$ of $\APUD(2k+3,m+2)$ to prove NP-hardness with vertical lines, and an instance $\Psi'$ of $\APUD(4k+3,0)$ to prove NP-completeness without vertical lines.
In $\Psi'$, only disks that can “jump” from one horizontal line to another are the ones that are on the top line of $\ell^{Ca}_1$ and  bottom line of $\ell'^{Cb}_1$.
And those jumps do not change the overall configuration.

[draw=none] at (-3.5,0) $\alpha$;

[draw=none] at (3.8,-12) $\ell_q$;
[draw=none] at (7.6,-12) $\ell_r$;
[draw=none] at (11.4,-12) $\ell_s$;
[draw=none] at (15.2,-12) $\ell_t$;

[draw=none] at (-3.5,-9) $\ell_\Delta$;
[draw=none] at (-3.5,-7.05) $\ell'_C$;
[draw=none] at (-3.5,-4.85) $\ell'_B$;
[draw=none] at (-3.5,-2.65) $\ell'_A$;
[draw=none] at (-3.5,2.65) $\ell_A$;
[draw=none] at (-3.5,4.85) $\ell_B$;
[draw=none] at (-3.5,7.05) $\ell_C$;
[draw=none] at (-3.5,9) $\ell_\nabla$;

every node=[draw, fill=black, shape=circle, minimum size=2pt,inner sep=0pt];

[thick] (-3,0)–(22,0);

ıin 0,1.9,3.8,5.7,7.6,9.5,11.4,13.3,15.2,17.1,19

at (ı,0) ;
(ı,0) circle[radius=1];

ıin 3.8,7.6,11.4,15.2

ȷin -7.6,-6.5,-5.4,-4.3,-3.2,-1.9,1.9,3.3, 4.4,5.5, 6.6,7.7

at (ı,ȷ) ;
(ı,ȷ) circle[radius=1];

ıin -7.6,-6.5,-5.4,-4.3,-3.2,-1.9,1.9,3.3, 4.4,5.5, 6.6,7.7
[red] (-3,ı)–(22,ı);

ıin 0,19

ȷin -7.6,-6.5,-5.4,-4.3,-3.2,-1.9,1.9,3.3, 4.4,5.5, 6.6,7.7

at (ı,ȷ) ;
(ı,ȷ) circle[radius=1];

ıin -7.05,-4.85,-2.65,2.65,4.85,7.05

at (1.5,ı) ;
at (-1.5,ı) ;
at (17.5,ı) ;
at (20.5,ı) ;
(1.5,ı) circle[radius=1];
(-1.5,ı) circle[radius=1];
(17.5,ı) circle[radius=1];
(20.5,ı) circle[radius=1];

[thick] (-3,9)–(22,9);
[thick] (-3,-9)–(22,-9);

ıin 0, 2.32, 4.38, 6.43, 8.48, 10.53, 12.58, 14.63, 16.68, 19

at (ı,9) ;
(ı,9) circle[radius=1];
at (ı,-9) ;
(ı,-9) circle[radius=1];

ıin 3.8,7.6,11.4,15.2

ȷin -9.8,9.8

at (ı,ȷ) ;
(ı,ȷ) circle[radius=1];

Realization of the graph given in Figure <ref> on a set of parallel lines.

To show that $\APUD(k,0)$ recognition is in NP, we need to prove that a given solution can be verified in polynomial time as well as any feasible input will have a solution that takes up polynomial space, with respect to the input size.
Thus, we show that for any graph $G \in \APUD(0,k)$, there exists an embedding where the disk centers are represented using polynomially many decimals with respect to the input size.

For the following lemmas, define the set $\mathcal{H} = \{0, h_1, h_2, \dots, h_k\}$ where each element of the set corresponds to the Euclidean distance between a horizontal line, and the $x$-axis.
Without loss of generality, we assume that the bottom-most line is $x$-axis itself, and $h_i < h_j$ iff $i<j$.

[Extension disk]
Let $A$ and $B$ a pair of intersecting unit disks centered at $(a,h_i)$ and $(b,h_j)$, respectively.
The extension disk $A_\EX$ of $A$ is a disk centered at $(a,h_i)$, with radius $2$.
Then, $(b,h_j)$ is contained inside $A_\EX$, and symmetrically, $(a,h_i)$ is contained inside the extension disk $B_\EX$ of $B$.

We give the trivial definition of extension disk for the sake of simplicity in the following lemmas.
Essentially, we claim that the center of a disk has some freedom of movement, and this freedom is determined by precisely two disks.
To show this dependence, we utilize the intervals on a line, defined by the intersection points between the extension disks with that line.

Consider a disk $A$ centered at $(a,h_i)$.
Each pair of extension disks, $B_\EX$ and $C_\EX$ that intersect $y = h_i$ line determines an interval $I_A$, in which the center of $A$ can move without changing the relationship among $A$, $B$, and $C$.

Let $\beta$ and $\gamma$ be two positive numbers, $B$ and $C$ be a pair of disks, and $B_\EX$ and $C_\EX$ be the extension disks, respectively.
Without loss of generality, let $(a-\beta, h_i)$ be the intersection point between $B_\EX$ and $y=h_i$ which is the closest intersection point to the center of $A$.
Similarly, let $(a+\gamma, h_i)$ be the intersection point between $C_\EX$ and $y=h_i$ which is the closest intersection point to the center of $A$.

If $A$ intersects both $B$ and $C$, then $I_A = [a-\beta, a+\gamma]$.
If $A$ intersects $B$ but not $C$, then $I_A = [a-\beta, a+\gamma)$.
If $A$ intersects $C$ but not $B$, then $I_A = (a-\beta, a+\gamma]$.
If $A$ intersects neither $B$ nor $C$, then $I_A = (a-\beta, a+\gamma)$.

Consider a disk $A$ centered at $(a,h_i)$, and assume that the Euclidean distance between any pair of parallel lines is different than $2$.
Let $I_A$ be an interval on $y = h_i$ line, in which the center of $A$ can move freely without changing the relationship between $A$ and any other disk.
Then, $I_A$ is determined by at most two extension disks that intersect $y = h_i$ line.

Let $p_1, p_2, \dots$ be the $x$-coordinates of the intersection points between $y=h_i$ line and extension disks that intersect $y = h_i$ line, such that $p_j < p_{j+1}$.
Suppose that $a \neq p_j$ for any $j$.
Then, there exists two intersection points whose $x$-coordinates are $p_j, p_{j+1}$ such that $p_j < a < p_{j+1}$ holds.
The interval $A_I$ is determined precisely by the extension disks whose intersection points are $(p_j,h_i)$ and $(p_{j+1}, h_i)$.

Observe that if $a = p_j$ holds for some $j$, this is the same case where $A$ intersects with the corresponding disk, say $B$.
Depending on the the center of $B$ being to the left or to the right of the center of $A$, the interval can still be defined by either the pair $p_{j-1}, p_j$ or $p_j,p_{j+1}$.

Now, let us show that the intervals are large enough if the disk centers have coordinates that are represented using polynomially many decimals.
We denote this interval by $I_A$ for the center of a disk $A$.
Let us refer to a number in the output as good number if its decimal representation has polynomially many decimals with respect to the input size, and refer to a number as bad number, otherwise.

Let $A$ be a disk centered at $(a,h_i)$, and let $B$ and $C$ be two disks that defines $I_A$.
If the centers of $B$ and $C$ are good numbers, then there exists a point $p$ in $I_A$, such that $p$ is also a good number.

Let $(b,h_j)$ and $(c,h_m)$ be the centers of $B$ and $C$, respectively.
Define $\delta_{ij} = |h_i - h_j|$, and define $\delta_{im} = |h_i - h_m|$.
The intersection points on the line $y = h_i$ are $(\sqrt{4-\delta_{ij}^2} - b, h_i)$ and $(\sqrt{4-\delta_{im}^2} - c, h_i)$.
And thus by Pythagorean theorem we have

\begin{align*}
&\left|(\sqrt{4-\delta_{ij}^2} - b) - (\sqrt{4-\delta_{im}^2} - c)\right|\\
=& \left|(b+c) + (\sqrt{4-\delta_{ij}^2} - \sqrt{4-\delta_{im}^2})\right|
\end{align*}

as the length of the interval $I_A$.

Since $b$ and $c$ are both good numbers, $b+c$ is also a good number.
So, even though the expression $(\sqrt{4-\delta_{ij}^2}- \sqrt{4-\delta_{im}^2})$ is a very small, it does not change the fact that there exists a number $p$ inside the interval $A_I$ that is represented with polynomially many decimals.
Therefore, $p$ is a good number.

The coordinates for the disk centers can be chosen in the form of $b + \Sigma_{i} \pm \sqrt{a_i}$, where $a_i = \sqrt{4-\delta_i^2}$ and $\delta_i$ is the distance between two of the given parallel lines, and $b$ is a good number.

Suppose that we shift all the disk centers as far left to right as possible.
This defines a partial order $D_1 \prec D_2 \prec \dots D_n$ of dependence among the disks.
Now, let us fix one disk, and then respect this partial order among other disks.

For each disk $D_{i}$ one of the following holds:

* The Euclidean distance between $D_i$ and $D_j$ is exactly $2$ for some $j < i$.

* There are two other disks, $D_j$ and $D_m$ for some $j,m <i$ that defines the interval for the center of $D_i$ (by Lemma <ref>).

In case (i) holds, then the center of $D_i$ has the exactly same $x$-coordinate with the center of $D_j$.
In case (ii) holds, then $a_i = \sqrt{4-\delta_i^2}$, and by Lemma <ref>, the center of $D_i$ can have an $x$-coordinate which is a good number.

Now, we finally can show that $\APUD(k,0)$ is in NP by utilizing the previous lemmas.

For every graph $G$ and a set of parallel lines $\mathcal{L}$, if $G$ can be realized on lines from $\mathcal{L}$ as unit disks, then there exists such a realization using polynomial number of decimals with respect to the input size.

Since the input consists of only horizontal lines, $y$-coordinates of every disk center is fixed.
It remains to prove that $x$-coordinates of the disks in a solution cannot be forced to be in very small intervals.
That is, if a solution consists of disks whose centers are bad numbers, then we can perturb the solution to a new solution contains only good numbers.
The algorithm described below guarantees existence of an embedding of $G$ on parallel lines as unit disks, whose centers are good numbers.

* Let $G_0, G_1, \dots, G_k$ denote the disjoint induced subgraphs of $G$, such that the vertices of $G_i$ correspond to the disks centered on line $y = h_i$.

* Embed $G_0$ on $x$-axis with small perturbations which results as all disks on $y=0$ having polynomially many decimals.

* For each $1 \leq i \leq k$; find an embedding of $G_i$ onto $y=h_i$ line by only considering neighbors from $\bigcup_{j<i}G_j$.

Let us now show that the algorithm is correct.

Observe that each $G_i$ is a unit interval graph, and by [91], we know that every unit interval graph has an embedding with polynomially many decimals.
Thus, we can embed $G_0$ on $x$-axis with small perturbations which results as all disks on $y=0$ having good number as their centers.

Now, consider $G_0 \cup G_1$.
If $h_1 > 2$, then $G_1$ is a standalone unit interval graph, without any relationship with $G_0$.
If, on the other hand, $h_1 \leq 2$, then by Lemma <ref> and Lemma <ref>, we know that every vertex of $G_1$ can be embedded on $h_1$ as unit disks, of whose centers are good numbers.

For each $2 \leq i \leq k$, the algorithm processes every $G_i$ with respect to the previous embeddings, and thus, by Lemma <ref>, $G_i$ has an embedding on $y = h_i$ as unit disks, whose centers are good numbers.
By Lemma <ref>, we know that the perturbations can be done in a way such that every disk keeps its relationships with the other disks.
Note that the number of lines is bounded by the number of disks, as empty lines do not have any effect on the embedding.
Thus, even if we have the coordinates on the line $y = h_k$ as nested square roots, the resulting coordinates will have $a(1 + 2 + \dots + 2^{k})$ bits where $a$ is a good number.
Thus, the coordinates can be represented by polynomially many decimals, and hence are good numbers.

Therefore, if $G$ has an embedding on parallel lines, then we can obtain an embedding that can be represented by polynomially many decimals with respect to the input by starting from $G_0$, and gradually moving up to $G_k$, processing each subgraph iteratively.

Every yes-instance of $\APUD(k,0)$ has a polynomial witness that can be verified in polynomial time

By Lemma <ref>, we know that for every graph that has a feasible embedding on $k$ parallel lines, there exists an embedding that takes up polynomial space in decimal representation with respect to the input size.
Then, it remains to verify whether the solution gives the intersection graph, and the disks are centered on given lines, which takes only polynomial number of usual arithmetic operations.

$\APUD(k,0)$ is NP-complete.

Directly follows by Theorem <ref>, Lemma <ref>, and Corollary <ref>.

At this point, we would like to pose the question whether the technique used in this section can also be used for the problem of recognizing $\APUD(k,m)$ to determine NP membership.

$\APUD(k,m)$ recognition is NP-complete.

§ APUD(1,1) RECOGNITION IS OPEN

In this section, we discuss a natural basis for $\APUD(k,m)$ recognition problem.
That is, $k = 1$, and $m = 1$.
For the sake of simplicity, we can assume that given two lines are the $x$-axis and the $y$-axis.
First, we give some forbidden induced subgraphs for $\APUD(1,1)$.
Namely, those subgraphs are 5-cycle ($C_5$), a 4-sun ($S_4$), and a 5-star ($K_{1,5}$).

every node=[draw, fill=black, shape=circle, minimum size=4pt,inner sep=0pt];
(A) at (0,4) ;
(B) at (2,2) ;
(C) at (1,0) ;
(D) at (-1,0) ;
(E) at (-2,2) ;

every node=[draw, fill=black, shape=circle, minimum size=4pt,inner sep=0pt];
(A) at (0,4) ;
(B) at (1,3) ;
(C) at (2,2) ;
(D) at (1,1) ;
(E) at (0,0) ;
(F) at (-1,1) ;
(G) at (-2,2) ;
(H) at (-1,3) ;

every node=[draw, fill=black, shape=circle, minimum size=4pt,inner sep=0pt];
(A) at (0,2) ;
(B) at (0,4) ;
(C) at (2,2) ;
(D) at (1,0) ;
(E) at (-1,0) ;
(F) at (-2,2) ;

Three induced subgraphs that cannot be embedded on $\APUD(1,1)$.

Consider two disks $A$ and $B$, centered on $(a,0)$ and $(b,0)$ with $a<0<b$.
If $|a| = |b|$, then another disk, $C$ that is centered on $(0,c)$ intersects either both, or none.

Consider the triangle whose corners are $(a,0)$, $(b,0)$, and $(0,c)$.
If $|a|=|b|$, then $\sqrt{a^2+c^2} = \sqrt{b^2+c^2}$ holds.
For $C$ to intersect $A$, $\sqrt{a^2+c^2} \leq 2$ must hold.
However, since $|a| = |b|$, if $\sqrt{a^2+c^2} \leq 2$ holds, then $\sqrt{b^2+c^2} \leq 2$ also holds.
Thus, $C$ intersects $A$ if, and only if $C$ intersects $B$.
For the same reason, if $\sqrt{a^2+c^2} > 2$ holds, then $\sqrt{b^2+c^2} > 2$ also holds.
Thus, $C$ does not intersect $A$ if, and only if $C$ does not intersect $B$.

$C_5, S_4, K_{1,5} \not\in\APUD(1,1)$.

Let $A,B,C,D,E$ be the disks that form an induced 5-cycle on two perpendicular lines,
with the intersections between the pairs $(A,B)$, $(B,C)$, $(C,D)$, $(D,E)$, $(E,A)$.
By the pigeon hole principle, three of these disks must be on the same line.
Without loss of generality, let $A$, $C$, and $D$ be on $y=0$ line with centers $(a,0)$ and $(c,0)$, and $(d,0)$, respectively.
Up to symmetry, assume that $a < 0 < c < d$.
The remaining two disks, $B$ and $E$ must be centered on $x=0$.
Without loss of generality, assume that $e < 0 < b$.
However, $E$ cannot intersect $D$ without intersecting $C$ by Lemma <ref>.
Therefore, a 5-cycle cannot be realized as unit disks on two perpendicular lines.

Let $A,B,C,D$ be the disks that form the central clique of an induced 4-sun on two perpendicular lines with.
By Lemma <ref>, two of these disks must be on one line, and the remaining two must be on the other line.
Without loss of generality, assume that $A$ and $C$ are on $y=0$ line, and $B$ and $D$ are on $x=0$ line.
Denote the centers of $A,B,C,D$ with $(a,0),(0,b),(c,0),(0,d)$, respectively, and assume that $a<0<c$ and $d<0<b$.
Let $X$ and $Y$ be two disks centered on two given perpendicular lines.
Assume that $X$ intersects $A,D$, and, $Y$ intersects $B,C$.
Clearly, $X$ and $Y$ should be on the same line, and on the different sides of the clique to avoid intersections with other rays.
By Lemma <ref>, if $|b|=|d|$, then $X$ cannot intersect $B$ or $D$ independently.
By Lemma <ref>, if $|b|<|d|$, then $X$ cannot intersect $D$ without intersecting $B$.
Similarly, if $|b| > |d|$, then $Y$ cannot intersect $B$ without intersecting $D$.
Therefore, a 4-sun cannot be realized as unit disks on two perpendicular lines.

Four rays $a,b,c,d$ of a 4-star $u;a,b,c,d$ must be on four different sides of the central vertex $u$.
To complete a 5-star, there must be one more ray, say $e$ centered on $(e,0)$.
If we can embed $e$ on one of the lines without intersecting any rays, then we can place another disk on $(-e,0)$ to form a $K_{1,6}$.
However, a $K_{1,6}$ cannot be realized as a unit disk graph.
Therefore, a 5-star cannot be realized as unit disks on two perpendicular lines.

A given graph $G$ can be embedded on $x$-axis and $y$-axis as a unit disk intersection graph, without using negative coordinates for the disk centers if, and only if $G$ is a unit interval graph.

In this proof, let us denote the class of graphs that can be embedded on $x$- and $y$- axes as unit disks, using positive coordinates only by ${(xy)}^+$.
We show that the disks on the $y$-axis can be rotated by $\pi/2$ degrees counterclockwise, and the intersection relationships can be preserved as given in $G$.

$\mathbf{G \in {(xy)}^+ \Rightarrow G \in \mathbf{UIG}:}$
Consider two disks, $A$ and $B$, whose centers are $(a,0)$ and $(0,b)$, respectively, where $a$ and $b$ are both positive numbers.
If $A$ and $B$ do not intersect, then $\sqrt{a^2 + b^2} > 2$.
After the rotation, the center of $B$ will be on $(-b,0)$.
The new distance between the centers is $a + b$.
Since $(a+b)^2 > a^2 + b^2 > 4$, the inequality $a + b > 2$ holds.

If $A$ and $B$ intersect, then $\sqrt{a^2 + b^2} \leq 2$.
After the rotation, it might still be the case that $a + b > 2$.
However, now we can safely move the center of $B$ and the other centers that have negative coordinates closer to the center of $A$, recovering the intersection.
Note that if a disk $C$ is centered in between the centers of $A$ and $B$ after the rotation, then both $A$ and $B$ must intersect $C$ by Lemma <ref>.

$\mathbf{G \in \mathbf{UIG} \Rightarrow G \in {(xy)}^+:}$
Since $G$ is a unit interval graph, we can assume that every interval is a unit disk, and the graph is embedded on $x$-axis.
Consider two disks, $A$ and $B$, whose centers are $(-a,0)$ and $(b,0)$, respectively, where $a$ and $b$ are both positive numbers.
If $A$ and $B$ are intersecting, then $a + b \leq 2$
Then, after the rotation, since $a + b \leq 2$ holds, then $\sqrt{a^2 + b^2} \leq 2$ also holds.

If $A$ and $B$ are not intersecting, then $a + b > 2$.
After the rotation $\sqrt{a^2 + b^2} \leq 2$ might hold, creating an intersection between $A$ and $B$.
However, we can simply shift the center of $A$ (along with the other centers that are on $y$-axis) far away from the center of $B$, separating $A$ and $B$.

Lemma <ref> shows that if we use only non-negative coordinates, then

$\APUD^{+}(1,1) = \APUD^{+}(1,0) = \UIG$.
This also applies if we use only non-positive coordinates.
Thus, a given $\APUD(1,1)$ can always be partitioned into two unit interval graphs.
Considering the embedding, one of these two partitions contains the disks that are centered on the positive sides of $x$- and $y$- axes, and the other partition contains the disks that are centered on the negative sides of $x$- and $y$- axes.

A graph $G \in \APUD(1,1)$ can be vertex-partitioned into four parts, such that any two form a unit interval graph.

Let $\Sigma(G)$ be an embedding of $G$ onto $x$- and $y$- axes as unit disks.
Denote the set of unit disks in $\Sigma(G)$ that are centered on the positive side of the $x$-axis, and the positive side of the $y$-axis by $\Sigma^+(G)$.
Similarly, denote the set of unit disks that are centered on the negative side of the $x$-axis, and the negative side of the $y$-axis $\Sigma^-(G)$.
By Lemma <ref>, both $\Sigma^+(G)$ and $\Sigma^-(G)$ yield separate interval graphs.
The vertices that correspond to the disks in $\Sigma^+(G)$ yield a unit interval graph, as well as the vertices that correspond to the disks in $\Sigma^-(G)$.
Note that in case there exists a disk which is centered at $(0,0)$, then it can be included in one of the partitions arbitrarily.
Therefore, we can vertex-partition $G$ into two unit interval graphs.

Up to this point, we showed that if a unit disk graph can be embedded onto two orthogonal lines, then it can be partitioned into two interval graphs.
However, this implication obviously does not hold the other way around.
Thus, we now identify some structural properties of $\APUD(1,1)$.

Consider four unit disks $A,B,C,D$, that are embedded onto $x$-axis and $y$-axis.
If they induce a $4$-cycle, then the centers of those disks will be at $(a,0)$, $(0,b)$, $(-c,0)$, $(0,-d)$, respectively, where $a,b,c,d$ are non-negative numbers.

For the upcoming lemma, we will utilize the observation given in Remark <ref>.
The lemma is an important step to describe a characterization of $\APUD(1,1)$.

Consider eight unit disks embedded onto $x$-axis and $y$-axis, around the origin, whose intersection graph contains two induced $4$-cycles.
Then, this intersection contains at least four 4-cycles, each with a chord, not necessarily as induced subgraphs.
Moreover, those 4-cycles are formed by pairs of disks on the same direction ($+x$, $+y$, $-x$, $-y$) with respect to the origin.

Let those $4$-cycles be $(A,B,C,D)$, and $(U,V,W,X)$, in counterclockwise order, precisely as given in Remark <ref>.
Consider the disks $A,B,C$ centered at $(a,0)$, $(0,b)$, $(-c,0)$, where $a,b,c$ are non-negative numbers.
Due to the configuration, $B$ intersects both $A$ and $C$, but $A$ and $C$ do not intersect.
If $a=0$, then by Lemma <ref>, $C$ intersect $A$ if it intersects $B$.
Thus, $a>0$, and by symmetry, $b,c>0$ holds.
Since $A$ intersects $B$, and $b>0$, then $a<2$ also holds.
Again, up to symmetry, $b,c < 2$ holds.

Now consider the disks $A,B,U,V$ centered at $(a,0)$, $(0,b)$, $(u,0)$, $(0,v)$, respectively.
With the same reasoning, $0<a,b,u,v<2$ holds.
Thus, the disks that are centered on the same axis intersect.
That is, $A$ and $U$, and, $B$ and $V$ intersect.
If $A$ and $V$ do not intersect, then $\sqrt{a^2 + v^2} > 2$.
Since $U$ and $V$ intersect, $\sqrt{u^2 + v^2} \leq 2$ holds, and $u < a$ should also hold.
Thus, by Lemma <ref>, $B$ and $U$ intersects.
Symmetrically, if $B$ and $U$ do not intersect, then $A$ and $V$ intersect.
With the same reasoning, since $B$ and $C$ intersect, $C$ and $V$ also intersect.
Therefore, these eight disks have four subsets, $\{A,B,U,V\}$, $\{B,C,V,W\}$, $\{C,D,W,X\}$, $\{D,A,X,U\}$, such that in each set, the induced graph is a $4$-cycle with at least one chord, which gives us four 4-cycles, each with a chord.

The given lemmas imply that for a connected graph $G \in \APUD(1,1)$, the following hold.

* $G$ does not contain either of 4-sun ($S_4$) or 5-star($K_{1,5}$) as an induced subgraph, and the largest induced cycle in $G$ is of length $4$  (by Lemma <ref>).

* $G$ can be vertex partitioned into into four parts, such that any two form a unit interval graph (by Lemma <ref>).

* Given two $4$-cycles, $(a,b,c,d)$ and $(u,v,w,x)$ in $G$, each one of the quadruplets $\{a,b,u,v\}$, $\{b,c,v,w\}$, $\{c,d,w,x\}$, and $\{d,a,x,u\}$ is either a diamond or a $K_4$ (by Lemma <ref>).

Although this characterization gives a rough idea about the structure of a graph $G \in \APUD(1,1)$, it is not clear whether this is a full characterization and the recognition can be done in polynomial time.
Note that the characterization is a necessary step through recognition, but it is not yet known whether it is sufficient.
Therefore, we state the following conjecture.

Given a graph $G$, it can be determined whether $G \in \APUD(1,1)$ in polynomial time.

Since the very essence oft this paper is restricting the solution space, we leave an open problem for the readers before finishing this section.
The following question can also be interpreted as instead of having two intersecting lines as the solution space, we have a vertical line, and a horizontal ray which is perpendicular to the line, and the origin of the ray is on the vertical line.

Can $\APUD(1,1)$ recognition be solved in polynomial time if the disk centers are not allowed to have negative $x$-coordinates?

CHAPTER: CONCLUSION

§ SUMMARY OF THE CONTRIBUTIONS

In this thesis, we tackled some combinatorial problems in the field of computational geometry.
We summarized our contribution to the literature in Table <ref>.

Paper     Chapter(s)     Summary of the paper

[30]    <ref> and <ref>    We designed an algorithm for producing a vertex-to-point guarding of funnels that is
optimal in the number of guards.
Also, we designed an algorithm for a vertex-to-point conflict-free chromatic guarding
for funnels, which gives only a small additive error
with respect to the minimum number of colors required.

[34]     <ref>    We showed that the problem of deciding 5-colourability for visibility graphs of simple polygons, is NP-complete.
We also showed that the 4-colouring problem can be solved for visibility graphs of simple polygons, in polynomial time,
whereas for visibility graphs of polygons with holes, it becomes NP-complete.

[5]     <ref>    We introduced the unit disk visibility graphs, showed that the visibility graphs are a proper subclass of the unit disk visibility graphs, and proved that the 3-coloring problem is  NP-complete both for unit disk segment visibility graphs and unit disk visibility graphs of polygons with holes.

[27]     <ref>     Studied a variation of unit disk recognition problem which requires the disk centers to be centered on pre-given straight lines instead of anywhere in the Euclidean plane, and showed that the problem is NP-hard when any pair of lines is  either parallel or perpendicular, and NP-complete when the lines are parallel to each other.

The contributions of this thesis to the literature.

In Chapter <ref>, we considered two combinatorial problems, namely, polygon guarding and conflict-free chromatic guarding, and studied their aspects on funnels, and weak visibility polygons.
The main purpose behind studying restricted types of polygons is to describe an inductive scheme to obtain a conflict-free chromatic guarding of a simple polygon.

We have described an algorithm for producing a vertex-to-point guarding of funnels that is
optimal in the number of guards.
We have also designed an algorithm for a vertex-to-point conflict-free chromatic guarding
for funnels, which gives only a small additive error with respect to the minimum number of colors required.

Moreover, we have given a simple efficient upper bound of $O(\log^2 n)$, for the special case of weak-visibility polygons.
This still leaves room for improvement down to $O(\log n)$, which is
the worst-case scenario already for funnels and which would match
the previous P2P upper bound for simple polygons of [15].
We believe that such an improvement is achievable by a more careful
distribution of the colours sets (and re-use of colours)
to the max funnels in Algorithm <ref>.

In Chapter <ref>, we dealed with the conflict-free chromatic guarding on the general polygons.
We have utilized the results on the chromatic guarding from Chapter <ref> in order to obtain a conflict-free chromatic guarding in a given simple polygon with $O(n \log^2 n)$ colors.

In addition, we have studied the proper coloring problem on the general polygons, and on the polygons with holes.
we have showed that the problem of deciding 5-colorability for visibility graphs of simple polygons, is NP-complete.
We have also showed that the 4-coloring problem can be solved for visibility graphs of simple polygons, in polynomial time,
whereas for visibility graphs of polygons with holes, it becomes NP-complete.
However, it still remains to be explored whether approximation or parameterized algorithms exist for coloring problems of visibility graphs of polygons.

In Chapter <ref>, we considered the visibility graphs of various geometric settings with real-world restrictions, i.e., two points can see each other only if they are close enough in the Euclidean plane, and there is no obstacle in-between.
Thus, we have introduced the concept of “unit disk visibility graphs,” which models the real-world scenarios more accurately compared to the conventional visibility graphs.

The phrase “unit disk” indicates that every point in the Euclidean plane has a range, modeled by unit disks.
Since the main motivation behind in Chapter <ref> and Chapter <ref> are wireless sensors, and wireless sensor networks are usually modeled by unit disk graphs, our results in this chapter can be interpreted as an intersection between the areas of visibility graphs and unit disk graphs.
We have studied three particular types of unit disk graphs, namely, unit disk visibility graphs of a set of line segments, simple polygons and polygons with holes.
We showed that the unit disk graphs are a proper subclass of unit disk point visibility graphs while they are neither a subclass nor a superclass of these classes.
Moreover, we proved that the visibility graphs are a proper subclass of the unit disk visibility graphs.

We have also studied the problem of proper coloring for the newly introduced graph class, and showed that the 3-coloring problem for unit disk segment visibility graphs, and for the unit disk visibility graphs of polygons with holes is NP-complete.

In Chapter <ref> and Chapter <ref>, we have studied the visibility graphs, and in Chapter <ref>, we have studied a proper superclass of visibility graphs – unit disk visibility graphs in order to model real-world restrictions of wireless sensors more accurately.
In Chapter <ref>, without steering away from our motivation based on wireless sensors, we study the “axes-parallel unit disk graphs.”
In this newly introduced class, we tackled the problem by restricting the solution space.
We restricted the disks to be centered on pre-given straight lines instead of anywhere in the Euclidean plane.
The result in this chapter revealed three main aspects of the problem.
First, we showed that if the disks are forced to be centered on straight lines of which any pair is either parallel or perpendicular, then the recognition problem is NP-hard.
Then, we showed that if any pair of the pre-given lines are parallel to each other, then the problem is NP-complete.
Finally, we showed that if there are only two lines that are perpendicular, then the recognition problem is interesting to study, yet does not yield trivial results.

Paper     Name of the Paper     Author's contributions

[30]    On conflict-free chromatic guarding of simple polygons    Collaborated with all the co-authors in the design of the algorithm that produces an approximate chromatic guarding for a given funnel (Algorithm <ref>), and collaborated with Petr Hliněný on the final form of the algorithm which generalizes this scheme to the general case (Algorithm <ref>).

[34]     On Colourability of Polygon Visibility Graphs    Collaborated with Bodhayan Roy in the design of the algorithm that decides whether a visibility graph of a simple polygon admits 4-coloring (Algorithm <ref>)

[5]     Unit Disk Visibility Graphs    Worked alone on the construction of the NP-completeness reductions for the 3-coloring problem on unit disk visibility graphs of line segments (Theorem <ref>) and polygons with holes (Theorem <ref>).

[27]     On embeddability of unit disk graphs onto straight lines     Single author paper.

The contributions of the author of this thesis to the associated papers.

In Table <ref>, we summarize the contribution of the author of this thesis to every paper that his name appears on.
For the sake of simplicity, instead of listing every lemma, theorem, etc. we have listed the core parts in which the author contributed to, and this list should be interpreted as “contribution to this part and the affiliated propositions of the corresponding part.”

§ OTHER RESEARCH

In this section, we mention two other publications which were not detailed in this thesis, but definitely worth mentioning.

§.§ Clique-Width of Point Configurations

First of these papers are entitled as “Clique-Width of Point Configurations” [33], which was published in Workshop on Graph-Theoretic Concepts in Computer Science on June 2020, and the extended version was accepted in Journal of Combinatorial Theory in June 2021.

In this paper, we have studied the famous structural width parameter clique-width on geometric point configurations.
We showed that the basic properties of this clique-width notion can be applied to a set of points in the plane, and we relate it to the monadic second-order logic of point configurations.
As an application, we have provided several linear FPT time algorithms for geometric point problems which are NP-hard in general.

The paper describes how clique-width can be used to measure “complexity” of the combinatorial structure of point configurations in the plane.
Promising applications of the clique-width of annotated point configurations include mainly parameterized algorithms for solving some generally hard problems in discrete geometry.

The author of this thesis has contributed to this paper by reviewing the literature and providing the combinatorial problems mentioned in the paper which demonstrate the significance and relevance of studying clique-width parameter on point sets.

§.§ On upward straight-line embeddings of oriented paths

The second paper we would like to mention is entitled as “On upward straight-line embeddings of oriented paths” [29], which was published in the proceedings of VII Spanish Meeting on Computational Geometry.

In this paper, we investigate upward straight-line embeddings of oriented paths.
Along the lines of similar results in the literature, we find a condition – related to the number of vertices in between sources and sinks of an oriented path – which guarantees that an oriented path satisfying the condition on nvertices admits an upward straight-line embedding  into  any $n$-point set in general position. We also show that the following holds for every $\varepsilon >0$.
We show that if $S$ is a set of $n$ points chosen uniformly at random in the unit square, and $P$ is an oriented path on at most $(1/3 - \varepsilon)n$ vertices, then with high probability, $P$ has an upward straight-line embedding into $S$.

The author of this thesis has contributed to this paper by describing an algorithm to obtain an upward straight-line embedding for a convex point set.
Based on this algorithm, the main theorem of the paper, which proves that a random set of points in the unit square admits an upward straight-line embedding with high probability.

§ CONCLUDING REMARKS

The visibility graphs have become more and more relevant as the recent technological advancements emphasize on the importance of wireless networks.
Studying the computational aspects of some combinatorial problems is needed for engineers to produce more efficient products.

The relationship between a pair of objects can be interpreted and modeled in many different ways.
We picked two major ones for our doctoral studies:
The visibility, which considers the obstacles between two object, and unit disk graphs, which considers the distance between two objects.
Moreover, we bridged the gap between these two models, and introduced a new concept which considers both the obstacles, and the distance.

Considering that the application areas and the scales of wireless networks vary dearly – from nanosensors which are injected into human body to giant satellites which communicate with us from space, we believe that our contributions to the literature can be considered worthwhile.

While our research is not backed up with real-world experiments,  the underlying theory is, or will be useful for the relevant applications.
Keeping that in mind, we look forward to seeing the technology which utilizes the theoretical results in this paper, creating new challenges to overcome.

[1]
O. Aichholzer, G. Aloupis, E. D. Demaine, M. Demaine, V. Dujmovic, F. Hurtado,
A. Lubiw, G. Rote, A. Schulz, D. Souvaine, and A. Winslow.
Convexifying Polygons Without Losing Visibilities.
In CCCG, 2011.

[2]
Z. Abel, V. Alvarez, E. D. Demaine, S. P. Fekete, A. Gour, A. Hesterberg,
P. Keldenich, and C. Scheffer.
Three Colors Suffice: Conflict-Free Coloring of Planar Graphs.
In ACM-SIAM Symposium on Discrete Algorithms, pages
1951–1963, 2017.

[3]
M. Abrahamsen, A. Adamaszek, and T. Miltzow.
The art gallery problem is \(\exists\) $\mathbb{R}$-complete.
In Proceedings of the 50th Annual ACM SIGACT Symposium on
Theory of Computing, pages 65–73, 2018.

[4]
A. Alomari, N. Aslam, W. Phillips, and F. Comeau.
Three-dimensional path planning model for mobile anchor-assisted
localization in Wireless Sensor Networks.
In Canadian Conference of Electrical and Computer Engineering,
pages 1–5, 2017.

[5]
D. Ağaoğlu and O. Çağırıcı.
Unit Disk Visibility Graphs.
In European Conference on Combinatorics, Graph Theory and
Applications, September 2021.

[6]
J. Aspnes, T. Eren, D.K. Goldenberg, A.S. Morse, W. Whiteley, Y.R. Yang, B.D.O.
Anderson, and P.N. Belhumeur.
A theory of network localization.
In IEEE Transactions on Mobile Computing, pages 1663–1678,

[7]
J. Abello, O. Egecioglu, and K. Kumar.
Visibility graphs of staircase polygons and the weak bruhat order, i:
from visibility graphs to maximal chains.
Discrete & Computational Geometry, pages 331–358, 1995.

[8]
P. Ashok, F. V. Fomin, S. Kolay, S. Saurabh, and M. Zehavi.
Exact Algorithms for Terrain Guarding.
ACM Trans. Algorithms, 14:1–20, 2018.

[9]
J. Aspnes, D. Goldenberg, and Y. R. Yang.
On the Computational Complexity of Sensor Network Localization.
In Algorithmic Aspects of Wireless Sensor Networks, pages
32–44, 2004.

[10]
K. I. Aardal, S. P. M. van Hoesel, A. M. C. A. Koster, C. Mannino, and
A. Sassano.
Models and solution techniques for frequency assignment problems.
Annals of Operations Research, 153:79–129, 2007.

[11]
S. N. Bhatt and S. S. Cosmadakis.
The complexity of minimizing wire lengths in VLSI layouts, 1987.

[12]
M. Berg, O. Cheong, M. Kreveld, and M. Overmars.
Computational Geometry: Algorithms and Applications, Third
Springer, 2008.

[13]
P. Bose, A. Dean, J. Hutchinson, and T. Shermer.
On rectangle visibility graphs.
In Graph Drawing, pages 25–44, 1996.

[14]
É. Bonnet and P. Giannopoulos.
Orthogonal terrain guarding is np-complete.
In 34th International Symposium on Computational Geometry,
pages 1–15, 2018.

[15]
A. Bärtschi, S. K. Ghosh, M. Mihalák, T. Tschager, and P. Widmayer.
Improved bounds for the conflict-free chromatic art gallery problem.
In Proceedings of the 30th annual Symposium on Computational
Geometry, pages 144–153, 2014.

[16]
P. Bhattacharya, S. K. Ghosh, and B. Roy.
Vertex Guarding in Weak Visibility Polygons.
In CALDAM: Algorithms and Discrete Applied Mathematics, pages
45–57, 2015.

[17]
P. Bhattacharya, S. K. Ghosh, and B. Roy.
Approximability of guarding weak visibility polygons.
Discrete Applied Mathematics, 228:109–129, 2017.

[18]
N. Biggs.
Perfect codes in graphs.
Journal of Combinatorial Theory, Series B, 15:289–296, 1973.

[19]
H. Breu and D. G. Kirkpatrick.
Unit disk graph recognition is np-hard.
Computational Geometry, pages 3–24, 1998.

[20]
B. Ben-Moshe, M. J. Katz, and J. S. B. Mitchell.
A Constant-Factor Approximation Algorithm for Optimal 1.5D Terrain
SIAM J. Comput., 36:1631–1647, 2007.

[21]
É. Bonnet and T. Miltzow.
Parameterized hardness of art gallery problems.
In 24th Annual European Symposium on Algorithms, pages 1–17,

[22]
É. Bonnet and T. Miltzow.
An Approximation Algorithm for the Art Gallery Problem.
In 33rd International Symposium on Computational Geometry,
pages 1–15, 2017.

[23]
H. Breu.
Algorithmic aspects of constrained unit disk graphs.
PhD thesis, University of British Columbia, 1996.

[24]
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.

[25]
A. Bärtschi and S. Suri.
Conflict-Free Chromatic Art Gallery Coverage.
Algorithmica, 68:265–283, 2014.

[26]
W. Burgard, C. Stachniss, M. Bennewitz, and K. Arras.
Robot Motion Planning–Introduction to Mobile Robotics.
course slides, Accessed: 2010-09-30.

[27]
O. Çağırıcı.
On embeddability of unit disk graphs onto straight lines.
In Computer Science in Russia, pages 184–197, June 2020.

[28]
B. N. Clark, C. J. Colbourn, and D. S. Johnson.
Unit disk graphs.
Discrete Mathematics, pages 165–177, 1991.

[29]
O. Çağırıcı, L. Casuso, C. Medina, T. Patino, M. Raggi,
E. Roldan-Pensado, G. Salazar, and J. Urrutia.
On upward straight-line embeddings of oriented paths.
In XVII Spanish Meeting on Computational Geometry, pages
49–52, July 2017.

[30]
O. Çağırıcı, S. K. Ghosh, P. Hliněný, and B. Roy.
On conflict-free chromatic guarding of simple polygons.
In COCOA, 2019.

[31]
J. Cardinal and U. Hoffmann.
Recognition and Complexity of Point Visibility Graphs.
Discrete & Computational Geometry, pages 164–178, 2017.

[32]
B. Chazelle.
Approximation and decomposition of shapes.
In Advances in Robotics 1: Algorithmic and Geometric Aspects of
Robotics, pages 145–185, 1987.

[33]
O. Çağırıcı, P. Hliněný, F. Pokrývka, and
A. Sankaran.
Clique-Width of Point Configurations.
In Workshop on Graph-Theoretic Concepts in Computer Science,
pages 54–66, June 2020.

[34]
O. Çağırıcı, P. Hliněný, and B. Roy.
On Colourability of Polygon Visibility Graphs.
In FSTTCS, 2017.

[35]
V. Chvátal.
A Combinatorial Theorem in Plane Geometry.
Journal of Combinatorial Theory, 18:39–41, 1975.

[36]
S.-H. Choi, S. Y. Shin, and K.-Y. Chwa.
Characterizing and recognizing the visibility graph of a
funnel-shaped polygon.
Algorithmica, pages 27–51, 1995.

[37]
D. P. Dailey.
Uniqueness of colorability and colorability of planar 4-regular
graphs are NP-complete.
Discrete Mathematics, pages 289–293, 1980.

[38]
M. de Berg, O. Cheong, M. Kreveld, and M. Overmars.
Computational Geometry: Algorithms and Applications.
Springer-Verlag, 3rd edition, 2008.

[39]
B. Dil, S. Dulman, and P. Havinga.
Range-Based Localization in Mobile Sensor Networks.
In Wireless Sensor Networks, pages 164–179, 2006.

[40]
P. Duchet, Y. Hamidoune, M. Las Vergnas, and H. Meyniel.
Representing a planar graph by vertical lines joining different
Discrete Mathematics, pages 319–321, 1983.

[41]
G. D. da Fonseca, V. G. Pereira de Sa, R. C. S. Machado, and C. M. H. de
On the recognition of unit disk graphs and the Distance Geometry
Problem with Ranges.
Discrete Applied Mathematics, pages 3–19, 2015.

[42]
A. A. Diwan and B. Roy.
On colouring point visibility graphs.
Discrete Applied Mathematics, 286:78–90, 2020.

[43]
H. Everett and D. G. Corneil.
Recognizing visibility graphs of spiral polygons.
Journal of Algorithms, pages 1–26, 1990.

[44]
A. Efrat and S. Har-Peled.
Guarding galleries and terrains.
Inf. Process. Lett., 100:238–245, 2006.

[45]
H. Everett, C.T. Hoàng, K. Kilakos, and M. Noy.
Planar segment visibility graphs.
Computational Geometry, pages 235–243, 2000.

[46]
M. El Khaili.
Visibility Graph For Path Planning In The Presence Of Moving
Engineering Science and Technology: An International Journal
(ESTIJ), pages 2250–3498, 2014.

[47]
L. H. Erickson and S. M. LaValle.
An Art Gallery Approach to Ensuring that Landmarks are
In Robotics: Science and Systems VII, pages 81–88, 2011.

[48]
W. Evans and N. Saeedi.
On characterizing terrain visibility graphs.
JoCG, pages 108–141, 2015.

[49]
S. Eidenbenz, C. Stamm, and P. Widmayer.
Inapproximability Results for Guarding Polygons and Terrains.
Algorithmica, 31:79–113, 2001.

[50]
S. P. Fekete, S. Friedrichs, M. Hemmer, J. B. M. Mitchell, and C. Schmidt.
On the Chromatic Art Gallery Problem.
In Canadian Conference on Computational Geometry, 2014.

[51]
S. P. Fekete and P. Keldenich.
Conflict-Free Coloring of Intersection Graphs.
In The International Symposium on Symbolic and Algebraic
Computation, pages 31:1–31:12, 2017.

[52]
F. V. Fomin, D. Lokshtanov, and S. Saurabh.
Bidimensionality and geometric graphs.
In ACM-SIAM Symposium on Discrete Algorithms, pages 1563–1575,

[53]
L. Floriani and P. Magillo.
Algorithms for Visibility Computation on Terrains: A Survey.
Environment and Planning B: Planning and Design, pages
709–728, 2003.

[54]
S. K. Ghosh and P. P. Goswami.
Unsolved Problems in Visibility Graphs of Points, Segments, and
ACM Comput. Surv., 2013.

[55]
S. K. Ghosh.
Visibility Algorithms in the Plane.
Cambridge University Press, 2007.

[56]
S. K. Ghosh.
Approximation algorithms for art gallery problems in polygons.
Discrete Applied Mathematics, 158:718–722, 2010.

[57]
M. R. Garey and D. S. Johnson.
Computers and Intractability: A Guide to the Theory of
W. H. Freeman & Co., New York, NY, USA, 1979.

[58]
M. Garey, D. Johnson, and H. So.
An application of graph coloring to printed circuit testing.
IEEE Transactions on Circuits and Systems, pages 591–599,

[59]
P. Gupta, B. Krishnamoorthy, and G. Dreifus.
Continuous toolpath planning in a graphical framework for sparse
infill additive manufacturing.
Computer-Aided Design, 127:102880, 2020.

[60]
M. Ghodsi, A. Maheshwari, M. Nouri Baygi, J.-R. Sack, and H. Zarrabi-Zadeh.
Comput. Geom. Theory Appl., pages 435–446, 2014.

[61]
S. K. Ghosh, A. Maheshwari, S. Prasant Pal, S. Saluja, and C.E. Veni
Characterizing and recognizing weak visibility polygons.
Computational Geometry, pages 213–233, 1993.

[62]
L. J. Guibas, R. Motwani, and P. Raghavan.
The robot localization problem.
SIAM Journal on Computing, 26:1120–1138, 1997.

[63]
S. K. Ghosh, T. Shermer, B. K. Bhattacharya, and P. P. Goswami.
Computing the maximum clique in the visibility graph of a simple
Journal of Discrete Algorithms, 5:524–532, 2007.

[64]
A. Gräf, M. Stumpf, and G. Weißenfels.
On coloring unit disk graphs.
Algorithmica, pages 277–293, 1998.

[65]
R. K. Guy.
Unsolved Problems in Number Theory.
Springer-Verlag, 1994.

[66]
J. Hershberger.
Finding the Visibility Graph of a Simple Polygon in Time
Proportional to Its Size.
In Proceedings of the Third Annual Symposium on Computational
Geometry, pages 11–20, 1987.

[67]
J. Hershberger.
Finding the visibility graph of a polygon in time proportional to
its size.
Algorithmica, 4:141–155, 1989.

[68]
T. Hayashi, A. Kawamura, Y. Otachi, H. Shinohara, and K. Yamazaki.
Thin strip graphs.
Discrete Applied Mathematics, 216:203–210, 2017.

[69]
F. Hoffmann, K. Kriegel, S. Suri, K. Verbeek, and M. Willert.
Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Art
In International Symposium on Computational Geometry,
volume 34, pages 421–435, 2015.

[70]
F. Hoffmann, K. Kriegel, S. Suri, K. Verbeek, and M. Willert.
Tight bounds for conflict-free chromatic guarding of orthogonal art
Computational Geometry, 73:24–34, 2018.

[71]
M. Hoffmann and C. D. TÃ³th.
Segment endpoint visibility graphs are hamiltonian.
Computational Geometry, pages 47–68, 2003.

[72]
J. P. Hutchinson.
Arc- and circle-visibility graphs.
Australas. J. Combin., pages 241–262, 2002.

[73]
H. Ito and M. Kadoshita.
Tractability and intractability of problems on unit disk graphs
parameterized by domain area.
In International Symposium on Operations Research and Its
Applications, pages 120–127, 2010.

[74]
A. Itai, C. Papadimitriou, and J. Szwarcfiter.
Hamilton paths in grid graphs.
SIAM Journal on Computing, 11(4):676–686, 1982.

[75]
G. Kant.
A More Compact Visibility Representation.
International Journal of Computational Geometry &
Applications, pages 197–210, 1997.

[76]
M. J. Katz.
A PTAS for vertex guarding weakly-visible polygons - an extended
CoRR, abs/1803.02160, 2018.

[77]
F. Khodakarami, F. Didehvar, and A. Mohades.
1.5D terrain guarding problem parameterized by guard range.
Theor. Comput. Sci., pages 65–69, 2017.

[78]
J. Kratochvíl and M. Křivánek.
On the Computational Complexity of Codes in Graphs.
In Mathematical Foundations of Computer Science 1988, volume
324, pages 396–404, 1988.

[79]
J. King and D. G. Kirkpatrick.
Improved Approximation for Guarding Simple Galleries from the
Discrete & Computational Geometry, 46:252–269, 2011.

[80]
J. Kahn, M. Klawe, and D. Kleitman.
Traditional Galleries Require Fewer Watchmen.
SIAM Journal on Algebraic Discrete Methods, pages 194–206,

[81]
V. Klee.
Is Every Polygonal Region Illuminable from Some Point?
The American Mathematical Monthly, pages 180–180, 1969.

[82]
M. J. Katz and G. Morgenstern.
Guarding Orthogonal Art Galleries with Sliding Cameras.
Int. J. Comput. Geometry Appl., 21:241–250, 2011.

[83]
R. J. Kang and T. Müller.
Sphere and dot product representations of graphs.
Discrete & Computational Geometry, 47:548–568, 2012.

[84]
F. Kuhn, T. Moscibroda, and R. Wattenhofer.
Unit Disk Graph Approximation.
In Joint Workshop on Foundations of Mobile Computing, pages
17–23, 2004.

[85]
J. Kára, A. Pór, and D. R. Wood.
On the Chromatic Number of the Visibility Graph of a Set of Points
in the Plane.
Discrete and Computational Geometry, pages 497–506, 2005.

[86]
D.-S. Kim, K. Yu, Y. Cho, D. Kim, and C. K. Yap.
Shortest Paths for Disc Obstacles.
In International Conference on Computational Science and its
Applications, pages 62–70, 2004.

[87]
J.-C. Latombe.
Robot Motion Planning.
Kluwer Academic Publishers, 1991.

[88]
D. T. Lee and A. K. Lin.
Computational Complexity of Art Gallery Problems.
IEEE Transactions on Information Theory, 32:276–282, 1986.

[89]
Y.-L. Lin and S. Skiena.
Complexity aspects of visibility graphs.
International Journal of Computational Geometry and
Applications, pages 289–312, 1995.

[90]
M. V. Marathe, H. Breu, H. B. Hunt, S. S. Ravi, and D. J. Rosenkrantz.
Simple heuristics for unit disk graphs.
Networks, pages 59–68, 1994.

[91]
F. McMorris.
Interval Graphs and Interval Orders.
Discrete Mathematics, 55:135–149, 1985.

[92]
S. Masuyama, T. Ibaraki, and T. Hasegawa.
The computational complexity of the m-center problems on the plane.
The Tran. of the Inst. of Electronics and Comm. Engineers of
Japan, E64(2):57–64, 1981.

[93]
C. McDiarmid and T. Müller.
Integer realizations of disk and segment graphs.
Journal of Combinatorial Theory, Series B, 103(1):114–143,

[94]
B. Oommen, S. Iyengar, N. Rao, and R. Kashyap.
Robot navigation in unknown terrains using learned visibility
graphs. Part I: The disjoint convex obstacle case.
IEEE Journal on Robotics and Automation, pages 672–681, 1988.

[95]
J. O'Rourke.
Art Gallery Theorems and Algorithms.
Oxford University Press, 1987.

[96]
J. O'Rourke.
In Handbook of Discrete and Computational Geometry, Second
Edition, pages 643–663. Chapman and Hall/CRC, 2004.

[97]
J. O'Rourke and K. Supowit.
Some NP-hard polygon decomposition problems.
IEEE Transactions on Information Theory, IT-29:181–190, 1983.

[98]
J. O'Rourke and I. Streinu.
The vertex-edge visibility graph of a polygon.
Computational Geometry, pages 105–120, 1998.

[99]
M. H. Overmars and E. Welzl.
New Methods for Computing Visibility Graphs.
In Proceedings of the Fourth Annual Symposium on Computational
Geometry, pages 164–171, 1988.

[100]
F. Pfender.
Visibility graphs of point sets in the plane.
Discrete & Computational Geometry, 39(1):455–459, 2008.

[101]
V. Raghavan and J. Spinrad.
Robust algorithms for restricted domains.
Journal of Algorithms, pages 160–172, 2003.

[102]
J. Saxe.
Embeddability of weighted graphs in k-space is strongly NP-Hard.
In Allerton Conference in Communications, Control and
Computing, pages 480––489, 1979.

[103]
T. J. Schaefer.
The Complexity of Satisfiability Problems.
In Symposium on Theory of Computing, pages 216–226, 1978.

[104]
A.-W. Scheer.
CIM Computer Integrated Manufacturing: Towards the Factory of
the Future.
Springer Science & Business Media, 2012.

[105]
T. Shermer.
Hiding People in Polygons.
Computing, 42:109–131, 1989.

[106]
S. Smorodinsky.
Conflict-Free Coloring and its Applications, pages 331–389.
Springer-Verlag, 2013.

[107]
A. Sánchez-Arroyo.
Determining the total colouring number is NP-hard.
Discrete Mathematics, 78(3):315–319, 1989.

[108]
J. Urrutia.
Chapter 22 - Art Gallery and Illumination Problems.
Elsevier, 2000.

[109]
R. A. Wilson.
Graphs, Colourings and the Four-Colour Theorem.
Oxford University Press, 2002.

[110]
R. Wein, J. P. van den Berg, and D. Halperin.
The visibility–voronoi complex and its applications.
Computational Geometry, pages 66–87, 2007.