Masaryk University

Faculty of Informatics

Computational Aspects of Problems on Visibility and Disk Graph Representations

Doctorate Dissertation

Onur Çağırıcı
Advisor: Prof. RNDr. Petr Hliněný, Ph.D.

Brno, August 2021

§ ACKNOWLEDGMENTS

During my time in Masaryk University, I have had the chance to meet with very exciting and great people.
I wouldn't have spent such an enjoyable and special time if it wasn't for them.

First of all, I would like to thank to my supervisor, Petr Hliněný as he generously allowed me to work under his supervision.
Thanks to his support and guidance, I have been able to pursue my research ideas with freedom and confidence.
Whenever I felt like I was stuck, Petr pushed me to the right direction and helped me to gain intuition about how to tackle challenging research problems.
Without him, I would not be able to complete this piece of work.

I also would like to thank my fellow colleague and officemate Bodhayan Roy for his friendship and support while he was a postdoctoral researcher at the Masaryk University.
Our discussions with Bodhayan have taught me how to be productive and precise while doing research.

While I was pursuing my doctoral degree, I also had great time with my friends. If it wasn't for the enjoyable times I spent with them during beautiful Brno evenings, I couldn't have found the motivation and courage to go back to work and finish this thesis.
So, thank you, my friends from Brno for all the booze you bought for me.

Although being away from their son were not very comfortable for them, my parents have always gave countenance to me while I was pursuing my PhD.
Thank you, mom, and thank you dad, for all the sacrifices you have made for me to achieve my academic goals.

Last, but absolutely not the least, I would like to thank Deniz, my significant other.
With her endless love and support, I was able to live in a very happy and peaceful environment.
She stood by me no matter what decision I have made, and gave her precious advice whenever I had the need.
I cannot ever overestimate her contributions to the process of preparation of this thesis, and my academic life.
Deniz, I cannot thank you enough for being such an essential part of my life.

This thesis focuses on two concepts which are widely studied in the field of computational geometry.
Namely, visibility and unit disk graphs.
In the field of visibility, we have studied the conflict-free chromatic guarding of polygons, for which we have described a polynomial-time algorithm that uses $O(n \log^2 n)$ colors to guard a polygon in a conflict-free setting, and proper coloring of polygon visibility graphs, for which we have described an algorithm that returns a proper 4-coloring for a simple polygon.
Besides, we have shown that the 5-colorability problem is NP-complete on visibility graphs of simple polygons, and 4-colorability is NP-complete on visibility graphs of polygons with holes.

Then, we move further with the notion of visibility, and define a graph class which considers the real-world limitations for the applications of visibility graphs.
That is, no physical object has infinite range, and two objects might not be mutually visible from a certain distance although there are no obstacles in-between.
To model this property, we introduce unit disk visibility graphs, and show that the 3-colorability problem is NP-complete for unit disk visibility graphs of a set of line segments, and a polygon with holes.

After bridging the gap between the visibility and the unit disk graphs, we then present our results on the recognition of unit disk graphs in a restricted setting – axes-parallel unit disk graphs.
We show that the recognition of unit disk graphs is NP-complete when the disks are centered on pre-given parallel lines.
If, on the other hand, the lines are not parallel to one another, the recognition problem is NP-hard even though the pre-given lines are axes-parallel (i.e. any pair is either parallel or perpendicular).

CHAPTER: INTRODUCTION

The field of computational geometry has gained attention drastically with the latest technological advancements.
Besides two very essential application areas, namely, computer graphics, and 3D design softwares, the computational geometry algorithms are also utilized in the fields of robotics [87], efficient 3D printing [59], geographic information systems [4], computer-integrated manufacturing [104], and many more [38].
In this thesis, we attempt to tackle the problems which concern the visibility relations and wireless networks.

A very famous visibility problem, called art gallery problem, has been studied for a long time along with its variations [95, 88, 15, 69].
The problem is simply placing guards into an art gallery, such that the guards can observe the whole gallery together.
While tackling this problem, the gallery is modeled as a simple polygon, and each guard is represented by a point in the polygon.

Until recently, the main focus for the art gallery problem and its variations was to minimize the number of guards used.
However, as the wireless technologies advanced, the very same problem is revisited with the motivation of robot motion planning via wireless communications [87].
As the wireless sensors became cheaper and cheaper, the objective of the problem has evolved into minimizing the number of unique frequencies used by the sensors, instead of minimizing the number of the guards.

This very problem constitutes the main motivation of our thesis, and is also closely related to frequency assignment problem in wireless networks [10, 25].
One can easily solve this problem by placing a sensor at each corner of the room, and assigning a different frequency to each sensor.
However, this method becomes very expensive as the number of sensors grow [10, 106].
Therefore, the main goal in this problem is minimize the number of different frequencies assigned to sensors.
Since the cost of a sensor is comparatively very low, we do not aim to minimize the number of sensors used.

Along with this application-based motivation, we also tackle a theoretical problem, colorability of polygon visibility graphs, which was left open by Ghosh [54] in 1995, and solved by  Çağırıcı, Hliněný, and Roy in 2017.
In this problem, every vertex of the given polygon corresponds to a vertex in the visibility graph, and two vertices of the graph are adjacent if, and only if the corresponding vertices see each other.

While dealing with the problems that are mentioned above, we also consider some restricted types of polygon, namely, funnels and weak-visibility polygons.
A funnel consists of two concave polygonal chains which meet at a common point at one end, and connected by an edge at the other end.
A weak-visibility polygon is a polygon which has a specific edge, of whose at least one point is visible from every other vertex.
Although these types of polygons seem an artificial to study on, there are indeed many applications which concern specifically those types of polygons [61, 36].

Since the main motivation of this thesis is based on the wireless sensor networks, we also remark that the conventional visibility relations fall short while modeling real-world scenarios, and suggest a new model to overcome this potential inaccuracy.
In the literature, two objects are said to be mutually visible when there are no obstacles in-between.
However, the “communication” between a pair of objects also depends on the distance between them, regardless of the type of the communication (visual, audio, data transfer, etc.).
This phenomenon is usually described by unit disk graphs [73, 23].

In an effort to bridge the gap between two important fields of study in computational geometry, namely, unit disk graphs and visibility the graphs, we introduce a new graph class: unit disk visibility graphs.
This class considers both the combinatorial problems concerning visibility relations and the limitations of the wireless sensors and is also a superclass of unit disk graphs.

We moreover study unit disk graph recognition problem [19] based on the motivation of theoretical aspects of wireless sensor networks [6].

The results presented in this thesis are published or will be published in the following conferences. 1, 2, and 4 are also submitted to high-quality journals, but the review process has not yet finished in the time of the submission of this thesis. Moreover, 4 has received the “Best Student Paper” award from the conference chair, and 5 has just been accepted to Journal of Combinatorial Theory, Series B (JCTB), which is a top journal in its field.

* O. Çağırıcı, P. Hliněný, B. Roy: On Colourability of Polygon Visibility Graphs in Foundations of Software Technology and Theoretical Computer Science (FSTTCS), December 2017 (Section <ref>).

* O. Çağırıcı, S. K. Ghosh, P. Hliněný, B. Roy: On Conflict-Free Chromatic Guarding of Simple Polygons in Combinatorial Optimization and Applications (COCOA), December 2019 (Sections <ref>, <ref>, and <ref>)

* D. Ağaoğlu and O. Çağırıcı: Unit Disk Visibility Graphs in European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), September 2021 (Chapter <ref>)

* O. Çağırıcı: On embeddability of unit disk graphs onto straight lines in Computer Science in Russia (CSR), June 2020 (Chapter <ref>)

* O. Çağırıcı, P. Hliněný, F. Pokrývka, A. Sankaran: Clique-Width of Point Configurations in Workshop on Graph-Theoretic Concepts in Computer Science (WG), June 2020 (outside of the main focus of this thesis, mentioned briefly in Chapter <ref>)

* O. Çağırıcı, L. Casuso, C. Medina, T. Patino, M. Raggi, E. Roldan-Pensado, G. Salazar, J. Urrutia: On upward straight-line embeddings of oriented paths in XVII Spanish Meeting on Computational
Geometry (ECG), July 2017 (outside of the main focus of this thesis, mentioned briefly in Chapter <ref>)

The contributions of the author of this thesis to the papers that are mentioned above are summarized in Table <ref>.

CHAPTER: PRELIMINARIES

§ ORGANIZATION OF THE CHAPTER

This chapter introduces necessary definitions and notations that we use throughout this thesis.
We generally use standard notations but some are slightly changed to fit into the context better.
In Section <ref>, we briefly introduce graphs and describe the definitions and notations we use.
In Section <ref>, we describe the visibility graphs, in Section <ref> we focus on the geometric aspects of the intersection graphs, and in Section <ref>, we define the problems we tackle.

§ GRAPHS

This section describes the fundamental graph theory terminology and notations.
Unless stated explicitly, a graph is always

* simple,

* undirected,

* unweighted,

* connected, and

* finite.

in this thesis.
Thus, in this section, all the definitions follow accordingly.

§.§.§ Vertex, edge and adjacency

A graph is an abstract data structure which defines the relationships among a set of objects.
Each object is represented by (usually) a circle which is referred to as a vertex or a node.
If two objects are related, then there exists an edge between the vertices which they are represented with, and is denoted by a line segment.
A graph $G$ is denoted by $G = (V, E)$ where $V$ is the set of vertices, and $E$ is the set of edges.
The vertices are named using numbers $1,2,\dots$ or letters $a,b,\dots$.
See Figure <ref> for an example graph whose vertices are denoted by letters.

every node=[draw, fill=white, shape=circle, minimum size=18pt,inner sep=0pt];
(a) at (0,0) $a$;
(b) at (0,1) $b$;
(c) at (0,2) $c$;
(d) at (1,0) $d$;
(e) at (1,1) $e$;
(f) at (1,2) $f$;
(g) at (2,0) $g$;
(h) at (2,1) $h$;

A graph with 8 vertices, labeled $a$ through $g$, and 12 edges.

An edge is denoted by the pair of vertices which it joins together.
In Figure <ref>, the vertices of the graph are $a$, $b$, $c$, $d$, $e$, $f$, $g$ and the edges of the graph are $ab$, $bc$, $bd$, $be$, $bf$, $ce$, $cf$, $dg$, $ef$, $eg$, $eh$, $gh$.
There exists an edge $ab$ between a pair $a$ and $b$ of vertices.
Thus, $a$ and $b$ are called adjacent vertices or neighbors, and the edge $ab$ is called incident to both $a$ and $b$.

The set of all the vertices that are adjacent to a vertex $v$ is called the neighborhood of $v$ and denoted by $N(v)$.
For instance, in Figure <ref>, $N(a) = \{b\}$ and $N(b) = \{a,c,d,e\}$.
Note that the neighborhood of a vertex does not include the vertex itself.
Although this set is informally referred to as the neighborhood, more specifically, it is the open neighborhood.
If we include $v$ in the neighborhood of $v$, then we have the closed neighborhood of $v$, which is denoted by $N[v]$.
That is, $N[v] = N(v) \cup \{v\}$.

§.§.§ Subgraphs

A subgraph $H = (V', E')$ of the graph $G$ is a graph whose vertex set $V' \subseteq V$ is a subset of $V$, and edge set $E' \subseteq E$ is a subset of $E$.
For instance, let $G$ be the graph given in Figure <ref>.
Then, $H =\left(\{b,c,e,f\}, \{bc, cf, fe, eb\}\right)$ is a subgraph of $G$.
An induced subgraph, on the other hand, must include every edge which connects a pair of vertices in the vertex subset.
This means that $H$ is not an induced subgraph without the edges $bf$ and $ce$.

§.§.§ Paths

Let us mention some special structures which might appear in graphs.
A path $P_n$ of length $n$ is a sequence of edges $(e_1, e_2, \dots, e_n)$ which joins a sequence of vertices without repetition.
Every edge in a path joins two vertices, and there exists no other edges between any pair of the vertices except $e_1,\dots,e_n$.
In Figure <ref>, $(ab,bd,dg,ge)$ is a 4-path, but it is not an induced path, as the edge $be$ exists in the graph.
An example of induced 4-path is $(ab,bd,dg,gh)$.
A path can be denoted by the sequence of the edges as well as the sequence of the vertices which it includes, i.e., $(ab,bd,dg,gh)$ and $(a,b,d,g,h)$ define the same substructure.
This substructure is also referred to as “a path between $a$ and $h$” and denoted by $\pi(a,h)$
The smallest possible path is a single vertex, and is denoted by $P_0$.

A shortest path $\Pi(u,v)$ between a pair $u$ and $v$ of vertices is a path whose length is not greater than any given $\pi(u,v)$ in the same graph.

§.§.§ Cycles

A cycle $C_n$ is simply a path of length $n$, plus one extra edge which joins the first vertex in the sequence with the last vertex in the sequence.
In Figure <ref>, the vertices $b,d,g,e$ together with the incident edges form an induced 4-cycle.
A graph without any cycles is called a tree.
In Figure <ref>, the vertices $a,b,d,e,h$ form a tree.
A shortest path tree $\textit{SPT}(u)$ of a vertex $u$ in a graph $G$ is a spanning tree of $G$ rooted at $u$, such that all paths between $u$ and any vertex $v \in \textit{SPT}(u)$ is a shortest path $\Pi^*_{uv}$ in $G$.

§.§.§ Complete graphs and cliques

A complete graph $K_n$ is a graph with $n$ vertices, in which every pair of vertices are adjacent.
When a graph $G$ has a subgraph $Q$ which is a complete graph, then $Q$ is referred to as a clique.
$Q$ is said to be a maximal clique if there exists no other vertex in the graph which is adjacent to every vertex in $Q$.
In other words, a maximal clique cannot be extended by adding other vertices.
A clique $Q$ is called a maximum clique if there exist no other cliques in the graph whose cardinality is strictly greater than $Q$.
In Figure <ref>, $b,c,e,f$ form a clique of size 4, which is also the maximum clique.
The smallest non-empty clique, $K_1$ is a single vertex.
Analogously, $K_2$ is an edge with two vertices, and $K_3$ is a 3-cycle ($C_3$).

§ GEOMETRY

§.§ Polygons

A polygon $\mathcal{P}$ is defined as a closed region in the Euclidean plane, bounded by a finite set $\{e_1, \dots, e_n\}$ of line segments that are referred to as edges of the polygon.
By definition, no pair of edges of a polygon intersect in the Euclidan plane.
Every consecutive pair $(e_i, e_{i+1})$ and specifically $(e_n, e_1)$ of line segments shares an endpoint.
These endpoints are called the vertices of the polygon.
Such a cyclic sequence of consecutive vertices is referred to as a polygonal chain.
The vertices are usually labeled by numbers $1,2,\dots$ in the clockwise order.

every node=[draw, fill=white, shape=circle, minimum size=3pt,inner sep=1pt];
(1) at (0,0);
(2) at (0,1.5);
(3) at (2,4);
(4) at (2.6,3);
(5) at (4,3);
(6) at (5,2.5);
(7) at (4,1.6);
(8) at (3.1,0.3);
(9) at (1.9,2.3);
(10) at (1,0);

[gray, opacity=0.3] (1) foreach ıin 2,...,10 –(ı) –cycle;
[thick] (1) foreach ıin 2,...,10 –(ı) –cycle;

[label=left:$1$] at (1) ;
[label=left:$2$] at (2) ;
[label=above:$3$] at (3) ;
[label=45:$4$] at (4) ;
[label=45:$5$] at (5) ;
[label=right:$6$] at (6) ;
[label=-45:$7$] at (7) ;
[label=-30:$8$] at (8) ;
[label=below:$9$] at (9) ;
[label=right:$10$] at (10) ;

A simple polygon with 10 vertices.

We give an example polygon in Figure <ref>.
The boundary edges are denoted by bold lines, and the vertices are denoted by small circles.
The interior of the polygon is shaded in our pictures.

Note that the above definition (as well as the polygon given in Figure <ref>) is a simple polygon, meaning that the boundary edges do not cross, and there are no “holes” in the polygon.
A hole inside a polygon is simply another polygon which acts as an obstacle that blocks the visibility.
The holes can be polygonal [110], disk [86] and even mobile [46].

every node=[draw, fill=white, shape=circle, minimum size=3pt,inner sep=1pt];
(1) at (0,0);
(2) at (2.5,3);
(3) at (4,5);
(4) at (7.5,1.25);
(5) at (7,0.5);
(6) at (4.5,1);

(h1) at (2.5,2);
(h2) at (4,3.5);
(h3) at (5,2.5);
(h4) at (3.5,2);

[gray, opacity=0.3] (1) foreach ıin 2,...,6 –(ı) –cycle;
[white] (h1) foreach ıin 2,...,4 –(hı) –cycle;

[thick] (1) foreach ıin 2,...,6 –(ı) –cycle;
[thick] (h1) foreach ıin 2,...,4 –(hı) –cycle;

[label=$1$] at (1) ;
[label=left:$2$] at (2) ;
[label=$3$] at (3) ;
[label=right:$4$] at (4) ;
[label=right:$5$] at (5) ;
[label=below:$6$] at (6) ;

[label=below:$h_1$] at (h1) ;
[label=right:$h_2$] at (h2) ;
[label=below:$h_3$] at (h3) ;
[label=below:$h_4$] at (h4) ;

A polygon with 6 vertices, and a hole with 4 vertices which is inside that polygon.

§.§ Visibility and guarding

We describe the visibility relation among a set of geometric objects using visibility graphs.
Visibility, despite having various meanings in daily usage, has a specific meaning when it comes to computational geometry.
A point $p$ in a polygon $\PP$ is said to be visible to another point object $q$, if the line segment $\overline{pq}$ drawn between $p$ and $q$ belongs to $\PP$. See Figure <ref> for an example.

every node=[draw, fill=white, shape=circle, minimum size=1pt,inner sep=1pt];
(1) at (0,0);
(2) at (1,1);
(3) at (2,0);
(4) at (0,1.01);
(5) at (2,1.01);
(6) at (0,0.5);
[dashed] (4)–(5);
[dashed] (5)–(6);
(i1) at (-1,1.5);
(i2) at (1,1.5);
(i3) at (3,1.5);

[thick] (i1)–(i2)–(i3)–(3)–(2)–(1)–(i1);
[gray, opacity=0.3] (i1)–(i2)–(i3)–(3)–(2)–(1)–(i1);

[label=left:$p$] at (4) ;
[label=right:$q$] at (5) ;
[label=left:$r$] at (6) ;

Two points $p$ and $q$ in a polygon see each other because $\overline{pq}$ is never outside the polygon, even though a vertex of the polygon is on the segment. However, $r$ and $q$ do not see each other because $\overline{rq}$ crosses the exterior of the polygon.

In Figure <ref>, we show an example room with five robots, $a$, $b$, $c$, $d$, $e$, and two security cameras $X$, $Y$ in it.
The visibility relations of the robots and the cameras are denoted by lines, and the walls of the room are denoted by thick lines.
As seen in the figure, $X$ only sees $a$ since $c$, $d$ and $b$ are on the other side of the wall, and $e$ is behind $a$.
Similarly, $b$ also cannot see $e$ because $d$ blocks the visibility.

(1) at (0,0);
(2) at (3,1.8);
(3) at (4,0);
(4) at (6.5,0.5);
(5) at (7,5);
(6) at (5.5,4);
(7) at (3,5);
(8) at (0,2);

[ultra thick] (1) foreach ıin 2,...,8 –(ı) – cycle;

every path=[draw, red];
(a) at (1.5,1.5);
(b) at (6,1.5);
(c) at (4.2,0.5);
(d) at (4.8,2.65);
(e) at (3.8,3.8);

every path=[draw, gray!80!blue];

every path=[draw, black];

Five robots, two cameras, and their visibility relations.

Note that in Figure <ref>, the visibility relations are defined in 2D.
In a real-world scenario, the cameras see everywhere in the room as they are usually installed close to the ceiling.
However, let us mention that in the scope of this thesis, we always assume that the visibility relations are defined in the Euclidean plane.
Moreover, unlike the picture shown in Figure <ref>, the visibility relations are defined between pairs of points.
Thus, an obstacle between two points $p$ and $q$ in a polygon $\PP$, is simply another point $o$, which lies on the line segment $\overline{pq}$ drawn between them, and is not a vertex of $\PP$.
The room, on the other hand, is modeled as a polygon (see Section <ref>).

Guarding a polygon $\mathcal{P}$ means placing a set of guards $\{g_1, \dots, g_k\}$ into $\mathcal{P}$ such that every point inside $\mathcal{P}$ is seen by at least one of the guards $g_i$ where $1 \leq i \leq k$.
In Figure <ref>, two cameras, $X$ and $Y$ are acting as guards and they are guarding the whole room given in Figure <ref> without the robots.

(1) at (0,0);
(2) at (3,1.8);
(3) at (4,0);
(4) at (6.5,0.5);
(5) at (7,5);
(6) at (5.5,4);
(7) at (3,5);
(8) at (0,2);

(X') at (6.904, 4.142);
(Y') at (0, 0.333);

[ultra thick] (1) foreach ıin 2,...,8 –(ı) – cycle;

[color=red, opacity=0.2] (X')–(5)–(6)–(7)–(8)–(1)–(2)–cycle;
[color=blue, opacity=0.2] (Y')–(1)–(2)–(3)–(4)–(5)–cycle;

Two cameras (guards) seeing the whole room. Orange part is seen (guarded) only by $X$, blue part is seen (guarded) only by $Y$, and the purple part is seen (guarded) by both of the cameras.

In general, for a polygon with $n$ vertices, $\lfloor n/3 \rfloor$ guards might be needed to guard the whole polygon [35].
When the guards are restricted to be on the vertices, finding the minimum number is an NP-hard problem [97].
We give details on this problem in Section <ref>

Based on the definition of visibility, we give the definitions of two restricted types of polygons, namely, funnels and weak-visibility polygons.

§.§.§ Funnels

A funnel is a special type of polygon which consists of two concave polygonal subchains $\mathcal{L} = (l_1, \dots, l_k)$ and $\mathcal{R} = (r_1, \dots, r_m)$ that meet at a vertex $l_k = r_m = \alpha$ called the apex, and a base edge $l_1r_1$ connecting the other ends of these chains.
In a funnel, a vertex can see only its two immediate neighbors from the same subchain, and some other vertices from the opposite subchain.
In Figure <ref>, we see an example funnel with 11 vertices where the length of the left and right polygonal chains are equal to 5.

every node=[draw, fill=white, shape=circle, minimum size=3pt,inner sep=1pt];
(1) at (0,0);
(2) at (0.6,0.1);
(3) at (1.1,0.5);
(4) at (1.5,1.2);
(5) at (1.8,2);
(6) at (1.9,2.8);
(7) at (2.05,2.2);
(8) at (2.3,1.5);
(9) at (2.8,0.8);
(10) at (3.6,0.2);
(11) at (4.5,0);

[gray, opacity=0.3] (1) foreach ıin 2,...,11 –(ı) –cycle;
[thick] (1) foreach ıin 2,...,11 –(ı) –cycle;

[label=left:$l_1$] at (1) ;
[label=above:$l_2$] at (2) ;
[label=135:$l_3$] at (3) ;
[label=left:$l_4$] at (4) ;
[label=left:$l_5$] at (5) ;
[label=above:$\alpha$] at (6) ;
[label=45:$r_5$] at (7) ;
[label=45:$r_4$] at (8) ;
[label=45:$r_3$] at (9) ;
[label=45:$r_2$] at (10) ;
[label=right:$r_1$] at (11) ;

A funnel with 11 vertices.

§.§.§ Weak-visibility polygons

A weak visibility polygon is a polygon where there exists an edge $e_c$, called a common edge, or a base edge such that every point inside the polygon sees at least one point on $e_c$.
The clockwise ordering on a weak-visibility polygon is usually given such that the common edge is the polygonal edge between the first and the last vertex.
In Figure <ref>, we see a weak-visibility polygon with 25 vertices where the edge between the vertices $1$ and $25$ is the common edge, and every other vertex sees at least one point on that edge.

every node=[draw, fill=white, shape=circle, minimum size=3pt,inner sep=1pt];
(1) at (0,0) ;
(2) at (6,0.9) ;
(3) at (7.9,2) ;
(4) at (8,6) ;
(5) at (7,8) ;
(6) at (4.3,9) ;
(7) at (5,11.5) ;
(8) at (7.8,9.5) ;
(9) at (11,8) ;
(10) at (15,8.5) ;
(11) at (15,11.5) ;
(12) at (14.5,13) ;
(13) at (16.5,12) ;
(14) at (18,13) ;
(15) at (19,10) ;
(16) at (19.5,9) ;
(17) at (23,8) ;
(18) at (24,10.5) ;
(19) at (24.2,12) ;
(20) at (26,11) ;
(21) at (31,10) ;
(22) at (28.6,8) ;
(23) at (27.5,6) ;
(24) at (25,1.5) ;
(25) at (31,0) ;

[gray, opacity=0.3] (1) foreach ıin 2,...,25 –(ı) –cycle;
[thick] (1) foreach ıin 2,...,25 –(ı) –cycle;

[label=left:$1$] at (1) ;
[label=135:$2$] at (2) ;
[label=135:$3$] at (3) ;
[label=left:$4$] at (4) ;
[label=-135:$5$] at (5) ;
[label=below:$6$] at (6) ;
[label=45:$7$] at (7) ;
[label=45:$8$] at (8) ;
[label=above:$9$] at (9) ;
[label=135:$10$] at (10) ;
[label=left:$11$] at (11) ;
[label=135:$12$] at (12) ;
[label=below:$13$] at (13) ;
[label=45:$14$] at (14) ;
[label=45:$15$] at (15) ;
[label=-135:$16$] at (16) ;
[label=135:$17$] at (17) ;
[label=135:$18$] at (18) ;
[label=135:$19$] at (19) ;
[label=45:$20$] at (20) ;
[label=135:$21$] at (21) ;
[label=-45:$22$] at (22) ;
[label=-45:$23$] at (23) ;
[label=135:$24$] at (24) ;
[label=above:$25$] at (25) ;

A weak-visibility polygon with 25 vertices.

§.§.§ Visibility graphs

A visibility graph is a simple graph $G = (V,E)$ defined over a set $\mathcal{S}$ of geometric entities where a vertex $u \in V$ represents a geometric entity $s_u \in \mathcal{S}$, and the edge $uv \in E$ exists if and only if $s_u$ and $s_v$ are mutually visible (or see each other).
In the literature, visibility graphs were studied considering various geometric sets such as the vertex set of a simple polygon [95], of a polygon with holes [110], a set of points [31], a set of line segments [45], a set of horizontal line segments [40], a set of rectangles [13], a set of arcs [72], along with different visibility models such as line-of-sight visibility [58], $\alpha$-visibility [60], $\pi$-visibility [108], and vertex-edge visibility [98].

When we consider the visibilities not only among discrete elements such as vertices of a polygon, but also the area which is visible from a point, then we cannot model such a scenario using graphs.
This is simply because there are uncountably infinitely many points in a given finite area, and if we attempt to draw a graph where vertices correspond to those points, then we end up with an infinite graph, which is out of the scope of this thesis.

§ INTERSECTION GRAPHS

In this section, we describe the intersection graphs.
For the definition of the fundamental graph theory terminology and notations, we refer the reader to Section <ref>.

An intersection graph is a graph $G = (V,E)$ such that a vertex $u \in V$ is a set, and there exists an edge $uv \in E$ if, and only if the sets $u$ and $v$ intersect.
The elements of these sets might be discrete, e.g. $\mathbb{N}$, $\mathbb{Z}^-$, $\{-23.0001, \sqrt{-13}, \pi,\}$ or continuous, e.g. $\mathbb{R}^+$, $\mathbb{I}$, $S = \{(x,y)\ | \ 0 <x\leq 100,\ -100 < y \leq 0 \}$.
Since a geometric entity (sphere, square, ellipse, line, etc.) is defined by a set of points, a graph which represents the intersection relations among a set of geometric entities is also referred to as an intersection graph.

§.§.§ Unit interval graphs

An interval on the number real is defined by a pair $(a,b)$ of real numbers, where $a < b$, and contains all the real numbers lying between $a$ and $b$.
That is, $(a,b) = \{x\in \mathbb{R}\ | \ a < x < b \}$.
If the interval is closed, then it is denoted by $[a,b]$, and thus written as  $[a,b] = \{x\in \mathbb{R}\ | \ a \leq x \leq b \}$.

In Figure <ref>, we see an interval on the real line.
The vertical short lines, labeled $a$ and $b$, denote the beginning and the end of the interval, respectively.
The horizontal long line is the interval itself, and the thin black line is the real line.

[scale = 2, endpoint/.style = rectangle, inner sep=0pt, minimum height=10pt, minimum width=0pt, line width=0.75mm, draw]

[<->] (-2,0) – (2,0);
[endpoint, draw= blue!30,label=below:$a$] (a) at (-1,0) ;
[endpoint, draw= blue!30,label=below:$b$] (b) at (1,0) ;
[line width=0.75mm, draw= blue!30] (a)–(b);

An interval $(a,b)$ on the real number line.

The intersection graph of a set of intervals is called an interval graph.

[scale = 2.5, endpoint/.style = rectangle, inner sep=0pt, minimum height=10pt, minimum width=0pt, line width=0.75mm, draw]

[endpoint, draw= blue!30] (a) at (-0.6,0) ;
[endpoint, draw= blue!30] (b) at (0.4,0) ;
[endpoint, draw= red!30] (c) at (0,0.4) ;
[endpoint, draw= red!30] (d) at (1,0.4) ;
[endpoint, draw= green!30] (e) at (0.2,0.2) ;
[endpoint, draw= green!30] (f) at (1.2,0.2) ;
[endpoint, draw= orange!30] (g) at (0.8,0) ;
[endpoint, draw= orange!30] (h) at (1.8,0) ;
[line width=0.75mm, draw=blue!30] (a)–(b);
[line width=0.75mm, draw=red!30] (c)–(d);
[line width=0.75mm, draw=green!30] (e)–(f);
[line width=0.75mm, draw=orange!30] (g)–(h);

[scale = 0.6]
every node=[draw, shape=circle, minimum size=6pt,inner sep=4pt];
[fill=red] (blue) at (0,5) ;
[fill=blue] (red) at (0,0) ;
[fill=green] (green) at (5,0) ;
[fill=orange] (orange) at (5,5) ;

(a) A set of intervals, and (b) the disk graph that corresponds to the set given in (a).

The disks in Figure <ref> are of same length.
In this case, we can simply assume that every interval has length 1, and then the graph is called a unit interval graph.

§.§.§ Unit disk graphs

A disk $\DD$ is a closed region in the Euclidean plane that is defined by a pair of coordinates $(x,y) \in \mathbb{R}^2$ and a radius $r \in \mathbb{R}$.
Formally, it is written as $\DD = \{(x,y) \in \mathbb{R}^2\ |\ (x-a)^2 + (y-b)^2 \leq r^2\}$.
In Figure <ref>, there is a disk with radius $r$ and centered at $(x,y)$.
The blue area is the interior of the disk, the black circle is the boundary of the disk, and the line segment of that is drawn from the center to a point on the boundary indicates the radius of $\DD$.

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

[fill=blue!30,draw=black] (0,0) circle (2cm);
[label=120:$(x,y)$]  at (0,0) ;
[draw=none,fill=none] at (1,0.3) $r$;

A disk centered at $(x,y)$ with radius $r$.

A disk is said to be open if the boundary is not an element of the disk.
We always assume that the disks are closed, that is, the disk contains also the boundary.

In Figure <ref> we see a set of disks, and a graph.
The color of a vertex indicates to which disk it corresponds to.
Two vertices are adjacent if, and only if the corresponding disks intersect.
Such a graph is called a disk graph.

[scale = 0.6]

[fill=blue,draw=black,opacity=0.3] (0,0) circle (2cm);
[fill=red,draw=black,opacity=0.3] (0,1.6) circle (2cm);
[fill=green,draw=black,opacity=0.3] (1.5,2.3) circle (2cm);
[fill=orange,draw=black,opacity=0.3] (-1.5,-2.3) circle (2cm);

[scale = 0.6]
every node=[draw, shape=circle, minimum size=6pt,inner sep=4pt];
[fill=blue] (blue) at (0,5) ;
[fill=red] (red) at (0,0) ;
[fill=green] (green) at (5,0) ;
[fill=orange] (orange) at (5,5) ;

(a) A set of disks in the Euclidean plane, and (b) the disk graph that corresponds to the set given in (a).

The disks in Figure <ref> are of same radius.
In this case, regardless of the actual radii, we can simply assume that every disk has radius 1, and then the graph is called a unit disk graph.

§.§.§ Unit disk visibility graphs

Unit disk graphs are the intersection graphs of a set of equal radius (or unit) disks in the Euclidean plane. Each vertex in the graph corresponds to a disk, and there exists an edge between a pair of vertices if the disks corresponding to that pair intersect.
Similar to visibility graphs, unit disk graphs have several applications, and they are mainly used to model sensor networks [28, 4, 39].

Transmitters that are embedded into robots, or on sensor nodes form a wireless sensor network that can be modeled using graph data structure.
In the graph of a sensor network, vertices correspond to sensor nodes, and edges correspond to their pairwise communication links.
Note that the sensors have limited sensing range, and a pair of nodes can transmit data to each other if and only if they are inside each others' communication range.

Based on the real world applications, we assume that if a pair of objects (sensors, cameras, guards etc.) are too far from each other, then they do not see each other.
To model this notion, we adapt the unit disk graph model.

Let $\PP$ be a simple polygon, and let $G$ be the visibility graph of $\PP$.
$G$ is called a unit disk visibility graph of $\PP$ if the existence of an edge $uv \in E$ means that $p_u$ and $p_v$ see each other, and the Euclidean distance between them is less than 1 unit.
In other words, an element of the geometric set cannot see another element if they are too far apart.
Note that in our previous definition of the unit disk graph, there exists an edge between two vertices, if the corresponding disks intersect. This means that a distance $\leq 2$ is enough. However, in Chapter <ref>, we study this problem with the motivation of wireless sensor networks.
For two sensor nodes to communicate, they must be inside each other's communication range.
Thus, instead of the radius, we assume that the diameter of a unit disk is one unit, for the sake of accuracy.

(0,0) to[grid with coordinates] (1.5,1);

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

(1) at (0,0) ;
(2) at (0.5,0.6) ;
(3) at (0.8,1) ;
(4) at (1.5,0.5) ;
(5) at (1.4,0.1) ;
(6) at (0.9,0.2) ;

every path=[red]

ıin 1,...,5

every path=[black, dashed]

(0,0) to[grid with coordinates] (1.5,1);

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

(1) at (0,0) ;
(2) at (0.5,0.6) ;
(3) at (0.8,1) ;
(4) at (1.5,0.5) ;
(5) at (1.4,0.1) ;
(6) at (0.9,0.2) ;

every path=[thick]

every path=[red]

ıin 1,2,4,5

every path=[black, dashed]

(0,0) to[grid with coordinates] (1.5,1);

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

(1) at (0,0) ;
(2) at (0.5,0.6) ;
(3) at (0.8,1) ;
(4) at (1.5,0.5) ;
(5) at (1.4,0.1) ;
(6) at (0.9,0.2) ;

[gray, opacity=0.3] (1.center)–(2.center)–(3.center)–(4.center)–(5.center)–(6.center)–(1.center);

every path=[thick]

every path=[red]

every path=[black, dashed]

(0,0) to[grid with coordinates] (1.5,1);

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

(1) at (0,0) ;
(2) at (0.5,0.6) ;
(3) at (0.8,1) ;
(4) at (1.5,0.5) ;
(5) at (1.4,0.1) ;
(6) at (0.9,0.2) ;

(h1) at (0.5,0.4) ;
(h2) at (0.8,0.7) ;
(h3) at (1,0.5) ;
(h4) at (0.7,0.4) ;

[gray, opacity=0.3] (1.center)–(2.center)–(3.center)–(4.center)–(h3.center)–(h2.center)–(h1.center)–(1.center);
[gray, opacity=0.3] (4.center)–(5.center)–(6.center)–(1.center)–(h1.center)–(h4.center)–(h3.center)–(4.center);

every path=[thick]

every path=[red]

every path=[black, dashed]

Unit disk visibility relations of (a) a set of points, (b) a set of line segments, (c) a simple polygon, and (d) a polygon with a hole.

Unit disk point visibility graphs directly follows from this definition while for unit disk segment and polygon visibility graphs, the additional constraints are the followings: $i)$ the edges of unit disk segment visibility graphs cannot to intersect any segment, and $ii)$ the edges of unit disk polygon visibility graphs must totally lie inside the polygon.

§.§.§ Axes-parallel unit disk graphs

Axes-parallel unit disk graph is a unit disk graph of a set of disks that are centered on axes-parallel straight lines.
The domain of axes-parallel straight lines is a set of lines in 2D, where the angle between a pair of lines is either $0$ or $\pi/2$.
This implies that the equation of a straight line is either $y = a$ if it is a horizontal line, or $x = b$ if it is a vertical line, where $a,b \in \mathbb{R}$.

The input for axes-parallel straight lines recognition problem contains two sets, $\mathcal{H},\mathcal{V} \subset \mathbb{R}$, where $\mathcal{H}$ contains the Euclidean distance of each horizontal line from the $x$-axis, and $\mathcal{V}$ contains the Euclidean distance of each vertical line from the $y$-axis.
Thereby in the domain that we use, each vertex is mapped either onto a vertical line, or onto a horizontal line.

We denote the class of axes-parallel unit disk graphs as $\APUD(k,m)$ where $k$ is the number of horizontal lines, and $m$ is the number of vertical lines.

§ COMPUTATIONAL COMPLEXITY AND SOME COMBINATORIAL PROBLEMS

§.§.§ Asymptotic computational complexity

We first introduce the notation that we use throughout this section.
The set $\Sigma = \{0,1\}$ is called an alphabet, and $\Sigma^*$ denotes the set of all strings obtainable from $\Sigma$.
Let $L \subseteq \Sigma^*$ be a language, and let $w \in \Sigma^*$ be a word.
Throughout this thesis, $\Sigma = \{0,1\}$ always holds, as we do not deal with singleton alphabets.
A decision problem $\QQ$ is to determine whether a given word $w \in \Sigma^*$ belongs to a language $L \subseteq \Sigma^*$ over the alphabet $\Sigma$.

Let $\AA$ be an algorithm, $n$ denote the size of the input given to $\AA$, and $f(n)$ be the maximum number of operations executed on any input of size $n$ before $\AA$ terminates.
$\AA$ is called a polynomial-time algorithm, if there exists a polynomial $p \in \mathbb{N}_0[X]$ such that, for all $n \in \mathbb{Z}^+$, $f(n) < p(n)$.
A Turing machine is an abstract machine which reads and writes on a tape, and is able to simulate the logic of any given algorithm via a finite state automaton.
A Turing machine can be deterministic, i.e. in any given situation, the machine performs at most one pre-determined action, or non-deterministic, i.e. in some situations, the machine might perform one of many actions [57].
This corresponds to the Turing machine having deterministic or non-deterministic controlling automaton.
The notion of complexity is defined over the Turing machine.

We now describe four complexity classes which we use throughout this thesis. Namely, P, NP, NP-complete, NP-hard, $\exists\mathbb{R}$, and $\exists\mathbb{R}$-complete.
Let $\QQ$ be a decision problem, and $Q$ be an instance of $\QQ$.

If $Q$ can be correctly decided via a polynomial-time deterministic Turing machine algorithm,
then we say that $\QQ$ is a polynomialtime problem, and we write “$\QQ$ is in P” or “$\QQ \in$ P.”
In other words, the complexity class P is the set of all decision problems that can be solved in polynomial time.

If, on the other hand, $Q$ can be correctly decided via a polynomial-time non-deterministic Turing machine algorithm,
then we say that $\QQ$ is a non-deterministic polynomial-time problem, or “$\QQ$ is an NP problem,” in short.
This is equivalent to saying that a given solution to a given instance of any NP problem can be verified in polynomial time.

The complexity class NP-hard is the set $\mathfrak{Q}$ of decision problem $\QQ$ such that there exists a polynomial time reduction from any other NP problem $\QQ'$ to the problem $\QQ$.
Precisely, $\forall \QQ \in \mathfrak{Q}$ and $\forall \QQ' \in \text{NP}$, there exists a polynomial-time reduction from $\QQ'$ to $\QQ$.
This means that if we had a polynomial-time solution to some NP-hard problem, then we would be able to solve any problem in NP in polynomial-time.

A problem $\QQ$ is NP-complete, if $\QQ$ is an NP-hard problem, and is in NP.

Another complexity class, $\exists\mathbb{R}$ (read as “existential reals”) is defined as follows.
A problem $\QQ$ is referred to as an $\exists\mathbb{R}$ problem if any given instance $Q$ of $\QQ$ can be reduced in polynomial time to deciding whether
a given multivariate polynomial has a solution over the real numbers.
Similar to the definition of NP-completeness, a problem $\QQ$ is called an $\exists\mathbb{R}$-complete problem if it is an $\exists\mathbb{R}$ problem, and there exists a polynomial-time reduction to an instance of one of  $\exists\mathbb{R}$ problems.
It is still an open problem whether $\exists\mathbb{R}$ problems are in NP.

From this point on, whenever we write “polynomial-time algorithm,” we mean “polynomial-time deterministic Turing machine algorithm.”
Analogously, an exponential-time algorithm refers to an algorithm which terminates after executing at most exponentially many operations on a deterministic Turing machine.

We should also note that although the complexity zoo has way more classes,
we only deal with three complexity classes in this thesis: P, NP, and $\exists\mathbb{R}$.

§.§.§ Proper coloring and chromatic number

Assigning a color to a vertex $v$ means labeling $v$ with a label $\ell \in \mathcal{L}$  from a given set $\mathcal{L}$ of labels.
Conventionally, colors are preferred over labels.
For the sake of simplicity and readability, we also accommodate ourselves to this convention and describe our results using colors instead of labels.
A vertex $v$ is said to have a unique color with respect to a set $U$ of vertices when $c(v) \neq c(u)\ \forall u \in U \setminus \{v\}$.

Let $c(v)$ denote the color of a vertex $v$ in a graph $G = (V,E)$.
A proper coloring of a graph is assigning colors to every vertex $v \in V$ in a graph $G = (V,E)$ such that for a pair $u,v \in V$, $c(u) = c(v)$ holds if, and only if $uv \not\in E$.
In other words, every vertex has a unique color among its closed neighborhood.
Chromatic number $\chi(G)$ of a graph $G$ is the minimum number of colors required to obtain a proper coloring of $G$.
The problem of determining the chromatic number, i.e. chromatic number problem, is an NP-complete problem [107].
Instead of finding the minimum number of colors to properly color a graph, if we ask “Can a given graph $G$ be properly colored by $k$ colors?” for some constant $k$, then this problem is called the  $k$-coloring problem.
For $k=1$ and $k=2$, the problem is trivial: a graph $G$ cannot be 1-colored if there exists a pair of adjacent vertices, and can be 2-colored if, and only if $G$ is a bipartite graph.
However, except a few graph classes, $k$-coloring problem remains NP-complete for any value of $k \geq 3$.
Note that if a graph is $k$ colorable, then it is always $k+c$ colorable for $c \in \mathbb{N}$.
Thus, if a graph is 3-colorable, it is also 4-colorable, but the converse does not apply.

§.§.§ Conflict-free coloring

A conflict-free coloring of a graph $G$ is assigning colors to some subset $U \subseteq V$ of vertices such that every vertex $v$ has at least one unique color (i.e. a color that does not repeat) in its closed neighborhood $N[v]$.

For a vertex $v$, if there exists no vertex $u \in N[v]$ such that color of $u$ is unique among $N[v] \setminus \{u\}$, then $v$ has a conflict.
Note that $u=v$ might hold here due to the definition of a closed neighborhood.
Note that a proper coloring of a graph is also a conflict-free coloring of that graph.

Similar to proper coloring problem, conflict-free coloring is also NP-complete for a large set of graph classes.
In the most general case, determining whether there exists a conflict-free coloring with only one color in NP-complete.
Following the same notation, we write that conflict-free chromatic number ${\chi_{CF}}(G)$ of  graph $G$ is the minimum number of colors needed to obtain a conflict-free coloring of $G$.

The conflict-free coloring problem was first studied by Biggs with the name perfect code, which is essentially conflict-free coloring of a graph using only one color [18, 78].
Later on, this topic arouse interest on polygon visibility graphs when the field of robotics became widespread [32, 62].

§.§.§ Polygon guarding

A point $g$ in a polygon $\mathcal{P}$ is said to be guarding a set of points (or an area) $Q$ inside $\mathcal{P}$ if for every $q \in Q$, $g$ and $q$ see each other.
The point $g$, which is chosen as a guard, might be an arbitrary point inside $\mathcal{P}$ as well as a vertex of $\mathcal{P}$.
In this thesis, we assume that our “guards” are only placed on the vertices of a polygon.

A polygon $\mathcal{P}$ is guarded if, and only if there exists a subset $\Gamma = \{g_1, g_2, \dots, g_k\}$ of vertices of $\mathcal{P}$ are selected as guards, and $\bigcup_{g \in \Gamma} \Sigma(G)$ covers the whole interior of $\mathcal{P}$.

Instead of guarding the whole interior, if our goal is to guard every vertex in a polygon, then we have a different problem.
The main difference is that the former one cannot be expressed as a simple graph, while the latter one can be, since the vertices of a graph are discrete geometric entities.
Thus, if the goal is to guard all the vertices, then a correct solution is referred to as vertex-to-vertex guarding.
On the other hand, if the goal is to guard the whole polygon, then a correct solution is referred to as vertex-to-point.

One of the best known problems  in computational geometry, the art gallery problem, is essentially a vertex-to-point guarding problem [38, 95].
The problem is to find the minimum number of guards to guard an art gallery, which is modeled by an $n$-vertex polygon.
This problem  was shown to be NP-hard by Lee and Lin [88] and more recently $\exists \mathbb{R}$-complete by Abrahamsen et al. [3].
The Art Gallery Theorem, proved by Chvátal, shows that $ \lfloor n/3 \rfloor$ guards are sufficient and sometimes necessary to guard a simple polygon [35].

The guard minimization problem has been studied under many constraints; such as the placement of guards being restricted to the polygonal perimeter or vertices [79],
the viewers being restricted to vertices, the polygon being terrains [8, 20, 44], weakly visible from an edge [17], with holes or orthogonal [49, 82, 14], with respect to parameterization [21], or with respect to approximability [76].
For most of these cases the problem remains hard, but interesting approximation algorithms have also been provided [56, 22].

§.§.§ Conflict-free guarding of a polygon

Let $\mathcal{P}$ be a polygon, and $\Gamma = \{g_1, g_2, \dots, g_k\}$ be the guard set which guard $\mathcal{P}$ as a whole.
Suppose that the guards are assigned colors, and when a point $o$ in $\mathcal{P}$ is guarded by some guard $g_i \in \Gamma$, we write “$o$ sees the color of $g_i$.”

That is, every guard receives a color, and every point inside the polygon must be guarded by at least one unique color.
In addition to above mentioned versions of the art gallery problem (or rather polygon guarding problem), some problems consider not the number of the guards, but the number of colors that are assigned to the guards.
The colors, depending on the scope, determine the types of the guards.
If any observer in the polygon sees at least one guard with a different type, then that polygon has a conflict-free chromatic guarding [25, 15, 70].
If every guard that sees any given observer is of different type, then that polygon has a strong chromatic guarding [47].

§.§.§ Graph recognition

Given a graph class $\CC$, and a graph $G$, the graph recognition problem is to determine whether $G$ belongs to the class $\CC$.
The class $\CC$ can be any subset of graphs, e.g. polygon visibility graph, bipartite graph, interval grah, unit disk graph, etc.
In our thesis, we deal with a variant of the unit disk graph recognition problem.

Analogous to the definition, the unit disk graph recognition problem is about deciding whether a given graph $G = (V,E)$ is a unit disk graph.
That is, determining whether there exists a mapping $\Sigma: V \to (\mathbb{R} \times \mathbb{R})$, such that each vertex is the center of a unit disk respecting the intersection property given by the edges of $G$.
The mapping $\Sigma$ is also called the embedding of $G$ by unit disks.
This problem is an $\exists\mathbb{R}$-complete problem [83, 93].

We, therefore, attack this problem by restricting the solution space for the disk centers.
In the conventional setting, the centers can be anywhere in the Euclidean plane.
We introduce the problem called axes-parallel unit disk graphs recognition.
In this problem, we use the domain of axes-parallel straight lines which is a set of lines in 2D, where the angle between a pair of lines is either $0$ or $\pi/2$.
This implies that the equation of a straight line is either $y = a$ if it is a horizontal line, or $x = b$ if it is a vertical line, where $a,b \in \mathbb{R}$.

The input for axes-parallel straight lines recognition problem contains two sets, $\mathcal{H},\mathcal{V} \subset \mathbb{R}$, where $\mathcal{H}$ contains the Euclidean distance of each horizontal line from the $x$-axis,
and $\mathcal{V}$ contains the Euclidean distance of each vertical line from the $y$-axis.
Thereby in the domain that we use, each vertex is mapped either onto a vertical line, or onto a horizontal line.
We denote the class of axes-parallel unit disk graphs as $\APUD(k,m)$ where $k$ is the number of horizontal lines, and $m$ is the number of vertical lines.
Formally, the input is a graph $G = (V,E)$, where $V = \{1,2,\dots,n\}$, and two sets $\mathcal{H}, \mathcal{V} \subset \mathbb{Q}$ of rational numbers with $|\mathcal{H}| = k$ and $|\mathcal{V}| = m$.
The task is to determine whether there exists a mapping $\Sigma: V \to  (\mathbb{R} \times \mathcal{H}) \cup (\mathcal{V} \times \mathbb{R})$ which is a unit disk realization of $G$.

CHAPTER: RESTRICTED TYPES OF POLYGONS

§ SUMMARY OF THE CHAPTER

In this chapter, study guarding problems mentioned in Section <ref> on two (restricted) types of polygons, namely the funnels and the weak visibility polygons (defined in Section <ref>).
We study the relation between those two types of polygons, and we describe our results concerning combinatorial problems on funnels and weak-visibility polygons.

* We describe an algorithm which returns the minimum number of guards for a funnel to be fully guarded (Algorithm <ref>).

* We show that the very same guard set can be used to obtain a conflict-free chromatic guarding of the funnel.

* We describe an approximation algorithm for vertex-to-point conflict-free chromatic guarding of a funnel, with only a constant ($+4$) additive error (Algorithm <ref>).

* We thus prove a direct two-way relation between the optimal number of guards and optimal number of colors needed in a funnel (Section <ref>).

* By generalizing the previously listed results, we show that every weak visibility polygon on $n$ vertices can be vertex-to-point conflict-free chromatic guarded with only $O (\log^2 n)$ guards (Algorithm <ref>).

Our results concerning the general visibility polygons is in Chapter <ref>.

§ RELATED WORK

Recall that the guarding of a polygon is placing “guards” into the polygon, in a way that the guards collectively can see the whole polygon.
It is usually assumed that a guard can see any point unless there is an obstacle or a wall between the guard and that point.

In this chapter, we consider the art gallery problem with conflict free guarding property.
In addition to above mentioned versions of art gallery problem (or rather polygon guarding problem), some problems consider not the number of the guards, but the number of colors that are assigned to the guards.
The colors, depending on the scope, determine the types of the guards.
If any observer in the polygon sees at least one guard with a different type, then that polygon has a conflict-free chromatic guarding [25, 15, 70].
If every guard that any given observer is of different type, then that polygon has a strong chromatic guarding [47].

In our thesis, we focus on the theoretical aspects of this problem.
However, we would like to describe a real-world scenario which, we think, might motivate the reader to both follow the manuscript and improve the current state of art for the sake of potential technological advancements.

Consider a scenario where a mobile robot traverses a room from one point to another, communicating with the wireless sensors placed on the corners of the room.
Even if the robot has full access to the map of the room, it cannot determine its location precisely because of accumulating rounding errors [26].
And thus it needs clear markings in the room to guide itself to the end point in an energy efficient way.
To guide a mobile robot with wireless sensors, two properties must be satisfied.
First one is, no matter where the robot is in the polygon, it should hear from at least one sensor. That is, the placed sensors must together guard the whole room and leave no place uncovered.
The second one is, if the robot hears from several sensors, there must be at least one sensor broadcasting with a frequency that is not reused by some other sensor in the range. That is, the sensors must have conflict-free frequencies.
If these two properties are satisfied, then the robot can guide itself using the deployed wireless sensors as landmarks.
This problem is also closely related to frequency assignment problem in wireless networks [10, 25].
One can easily solve this problem by placing a sensor at each corner of the room, and assigning a different frequency to each sensor.
However, as we have mentioned in Chapter <ref>, this method becomes very expensive as the number of sensors grow [10, 106].
Therefore, the main goal in this problem is minimize the number of different frequencies assigned to sensors.
Since the cost of a sensor is comparatively very low, we do not aim to minimize the number of sensors used.
This notion justifies the conflict-free coloring version of the problem.

The above scenario is geometrically modeled as follows.
The room is a simple polygon with $n$ vertices.
There are $m$ sensors placed in the polygon (usually on some of its vertices),
and two different sensors are given two different colors if, and only if they broadcast in different frequencies.

§ FUNNELS

In this section, we focus on a special interesting type of polygons – funnels (defined in Section <ref>).
A polygon $\PP$ is a funnel if, and only if precisely three of the vertices of $\PP$ are convex, and two of the convex vertices share one common edge – the base of the funnel $\PP$.
We denote a funnel by $\FF$ throughout this section.

We use some special notation here. See Figure <ref>.
Let the given funnel be $\FF$, oriented in the plane as follows.
On the bottom, there is the horizontal base of the funnel – the line segment $\lseg{l_1}{r_1}$ in the picture.
The topmost vertex of $\FF$ is called the apex, and it is denoted by $\alpha$.
There always exists a point $x$ on the base which can see the apex $\alpha$, and then $x$ sees the whole funnel at once.
The vertices on the left side of apex form the left concave chain, and analogously, the vertices on the right side of the apex form the 				right concave chain of the funnel.
These left and right concave chains are denoted by $\mathcal{L}$ and $\mathcal{R}$ respectively.
We denote the vertices of $\mathcal{L}$ as $l_1, l_2, \ldots, l_k$ from bottom to top.
We denote the vertices of $\mathcal{R}$ as $r_1, r_2, \ldots, r_m$ from bottom to top.
Hence, the apex is $l_k = r_m = \alpha$.

§.§ Guarding a funnel

every node=[draw, shape=circle, minimum size=5pt,inner sep=0pt];
[label=$l_1$] (A) at (1.93,4.71) ;
[label=$l_2$,fill=red] (B) at (5,5) ;
[label=$l_3$] (C) at (8.72,6.76) ;
[label=$l_4$] (D) at (10.61,8.21) ;
[label=120:$l_5$] (E) at (13.01,10.71) ;
[label=left:$l_6$] (F) at (14.37,12.5) ;
[label=$\alpha$] (G) at (16.25,16.99) ;
[label=30:$r_7$] (H) at (16.83,14.37) ;
[label=30:$r_6$] (I) at (17.33,13.05) ;
[label=right:$r_5$] (J) at (19.22,10.8) ;
[label=$r_4$] (K) at (22.1,8.49) ;
[label=$r_3$,fill=blue] (L) at (23.5,7.58) ;
[label=$r_2$] (M) at (28,5.1) ;
[label=$r_1$] (N) at (29,4.71) ;

(A') at (24.71,6.89);
[minimum size = 3pt, fill=black, label=40:$~p$] (B') at (18.63, 11.46) ;
(C') at (17.25, 13.27);
[minimum size = 3pt, fill=black, label=150:$q~$] (M') at (14.7,13.25) ;

[very thick, color=red, dashed] (B)–(B');
[very thick, color=blue, dashed] (L)–(M');
[minimum size = 3pt, fill=black, label=270:$t$] (B'M') at (18,11.15) ;

A funnel $\FF$ with seven vertices in $\mathcal{L}$ labeled $l_1,
\ldots, l_7$ from bottom to top, and eight vertices in $\mathcal{R}$
labeled $r_1, \ldots, r_8$, including the apex $\alpha = l_7 = r_8$.
The picture also shows
the upper tangent of the vertex $l_2$ of $\mathcal L$ (drawn in
dashed red), the upper tangent of the vertex $r_3$ of $\mathcal R$
(drawn in dashed blue), and their intersection $t$.

We first consider the problem of minimizing the total number of vertex guards needed to guard all points of a funnel.
We start by describing a simple procedure (Algorithm <ref>) that provides us with a guard set which may not always be optimal (but very close to the optimum, see Corollary <ref>).
This procedure will be helpful for the subsequent coloring results.
Then, we also refine the simple procedure to compute the optimal number of guards
in Algorithm <ref>.

Let $l_i$ be a vertex on $\mathcal{L}$ which is not the apex.
We define the upper tangent of $l_i$, denoted by $\uptan(l_i)$, as the ray whose origin is $l_i$ and which passes through $l_{i+1}$.
Upper tangents for vertices on $\mathcal{R}$ are defined analogously.
Let $p$ be the point of intersection of $\mathcal{R}$ and the upper tangent of $l_i$.
Then we define $\upseg(l_i)$ as the line segment $\lseg{l_{i+1}}p$.
For the vertices of $\mathcal{R}$, $\upseg$ is defined analogously:
if $q$ is the point of intersection of $\mathcal{L}$ and the upper tangent of
$r_j \in \mathcal{R}$, then let $\upseg(r_j) := \lseg{r_{j+1}}q$.
See again Figure <ref>.

A funnel $\FF$ with concave chains $\mathcal{L}=(l_1,
\ldots, l_k)$ and $\mathcal{R}=(r_1, \ldots, r_m)$.
A vertex set guarding all the points of $\FF$.
Initialize an auxiliary digraph $G$ with two dummy vertices $x$ and $y$,

Initialize $\ES{S} \gets \{x\}$
$\ES{S}$ is not empty

Choose an arbitrary $t \in \ES{S}$, and remove $t$ from $\ES{S}$
Let $s=\upseg(t)$	*$s$ is a segment inside $\FF$
Let $q$ and $p$ be the ends of $s$ on $\mathcal{L}$ and $\mathcal{R}$, respectively
Let $i$ and $j$ be the largest indices such that $l_i$ and
$r_j$ are not above $q$ and $p$, resp.
$l_{i+1}$ can see whole $s$$i' \gets i+1$
(*[f]the topmost vertex on the left seeing whole $s$)
$i' \gets i$
$r_{j+1}$ can see whole $s$$j' \gets j+1$
(*[f]the topmost vertex on the right seeing whole $s$)
$j' \gets j$
Include the vertices $l_{i'}$ and $r_{j'}$ in $G$

Add the directed edge $(t,z)$ to $G$
segment $\upseg(z)$ includes the apex $l_k=r_m$
Add the directed edge $(z,y)$ to $G$
*$y$ is the dummy vertex
(*[f]more guards are needed above $z$)
$\ES{S}\gets \ES{S}\cup\{z\}$

Enumerate a shortest path from $x$ to $y$ in $G$
Output the shortest path vertices without $x$ and $y$ as the required guard set
Simple vertex-to-point guarding of funnels (uncolored).

The underlying idea of Algorithm <ref> is as follows.
Imagine we proceed bottom-up when building the guard set of a funnel $\FF$.
Then the next guard is placed at the top-most vertex $z$ of $\FF$,
nondeterministically choosing between $z$ on the left and the right chain of
$\FF$, such that no “unguarded gap” remains below $z$.
Note that the unguarded region of $\FF$ after placing a guard at $z$
is bounded from below by $\upseg(z)$.
The nondeterministic choice of the next guard $z$ is encoded within a digraph,
in which we then find the desired guard set as a shortest path.
The following is straightforward.

Algorithm <ref> runs in polynomial time, and it outputs
a feasible guard set for all the points of a funnel $\FF$.

As for the runtime, we observe that the number of considered line segments
$s$ in the algorithm is, by the definition of $\upseg$,
bounded by at most $k+m$ (and it is typically much lower than this bound).
Each considered segment $\upseg(t)$ of $t \in \ES{S}$ is processed at most once, and it contributes two edges to $G$.
Overall, a shortest path in $G$ is found in linear time.

We prove feasibility of the output set by induction.
Let $(x=x_0,x_1,\ldots,x_{a-1},$ $x_a=y)$ be a path in $G$.
We claim that, for $0\leq i\leq a$, guards placed at $x_0,x_1,\ldots,x_i$ guard all the points of $\FF$ below $\upseg(x_i)$.
This is trivial for $i=0$, and it straightforwardly follows by induction:
Algorithm <ref> asserts that $x_i$ can see whole $\upseg(x_{i-1})$, and $x_i$ hence also sees the strip between $\upseg(x_{i-1})$ 			and $\upseg(x_{i})$ by basic properties of a funnel.
Finally, at $x_{a-1}$, we guard whole $\FF$ up to its apex.

Unfortunately, the guard set produced by Algorithm <ref> may not be optimal under certain circumstances.
See the example in Figure <ref>; the algorithm picks the four red vertices, but the funnel can be guarded by the three green 				vertices.
Nevertheless, this (possibly non-optimal) guard set will be very useful in the next section in the context of conflict-free coloring.

[xscale=0.255, yscale= 0.33]

every node=[draw, shape=circle, minimum size=5pt,inner sep=0pt];
[label=$l_1$] (A) at (-23,0) ;
[fill=red, label=$l_2$] (B) at (-18.5,0.5) ;
[label=$l_3$] (C) at (-16,1) ;
[fill=green!80!black, label=150:$l_4~$] (D) at (-9.4,2.8) ;
[label=150:$l_5$] (E) at (-7.3,4.2) ;
[label=150:$l_6$] (F) at (-3.5,7) ;
[fill=red, label=150:$l_7$] (G) at (-2,8.5) ;
[fill=green!80!black, label=150:$l_8$] (H) at (-0.5,13) ;
[fill=red, label=right:$~l_9=r_9$] (I) at (0,17) ;

[label=$r_1$] (Q) at (23,0) ;
[label=$r_2$] (P) at (18.5,0.5) ;
[label=$r_3$] (O) at (16,1) ;
[fill=green!80!black, label=30:$r_4$] (N) at (9.4,2.8) ;
[fill=red, label=30:$r_5$] (M) at (7.3,4.2) ;
[label=30:$r_6$] (L) at (3.5,7) ;
[label=30:$r_7$] (K) at (2,8.5) ;
[label=30:$r_8$] (J) at (0.5,13) ;

(A') at (10.2,3.7);
(Q') at (-10.2,3.7);

(B') at (6.5,5.5);
(P') at (-6.5,5.5);
(C') at (5.5,6.8);
(O') at (-5.5,6.8);

(D') at (2,10.5);
(N') at (-2,10.5);

(E') at (1.9, 11);
(M') at (-1.9, 11);
(F') at (1.4, 12);
(L') at (-1.4, 12);

(G') at (0.4,15.7);
(K') at (-0.4,15.7);

(H') at (3.61, 5.6);
(J') at (-3.61, 5.6);

[color=gray, dashed] (A)–(A');
[color=gray, dashed] (Q)–(Q');
[color=gray, dashed] (D)–(D');
[color=gray, dashed] (N)–(N');
[color=gray, dashed] (E)–(E');
[color=gray, dashed] (F)–(F');
[color=gray, dashed] (M)–(M');
[color=gray, dashed] (L)–(L');
[color=gray, dashed] (B)–(B');
[color=gray, dashed] (C)–(C');
[color=gray, dashed] (P)–(P');
[color=gray, dashed] (O)–(O');
[color=gray, dashed] (G)–(G');
[color=gray, dashed] (K)–(K');

[thick]  (A)–(B)–(C)–(D)–(E)–(F)–(G)–(H)–(I)–(J)–(K)–(L)–(M)–(N)–(O)–(P)–(Q)–(A);

A symmetric funnel with $17$ vertices.
The gray dashed lines show the upper tangents of the vertices.
It is easy to see that Algorithm <ref> selects $4$ guards,
up to symmetry, at $l_2,r_5,l_7,l_9$ (the red vertices).
However, the whole funnel can be guarded by three guards
at $l_4,r_4,l_8$ (the green vertices), and it will be the task of
Algorithm <ref> to consider such better possibility.

For the sake of completeness, we now refine the simple approach of Algorithm <ref> to always produce a minimum size guard set.
Recall that Algorithm <ref> always places one next guard based on the position of the previous one guard.
Our refinement is going to consider also pairs of guards (one from the left and one from the right chain) in the procedure.
We correspondingly extend the definition of $\upseg$ to pairs of vertices as follows.
Let $l_i$ and $r_j$ be vertices of $\FF$ on $\mathcal{L}$ and $\mathcal{R}$, respectively, such that $\upseg(l_i)=\lseg{l_{i+1}}p$ intersects
$\upseg(r_j)=\lseg{r_{j+1}}q$ in a point $t$ (see in Figure <ref>).
Then we set $\upseg(l_i,r_j)$ as the polygonal line (“$\vee$-shape”) $\lseg pt\cup\lseg qt$.
In case that $\upseg(l_i)\cap\upseg(r_j)=\emptyset$, we simply define
$\upseg(l_i,r_j)$ as the upper one of $\upseg(l_i)$ and	$\upseg(r_j)$.

Algorithm <ref>, informally saying,
enriches the two nondeterministic choices of placing the next guard
in Algorithm <ref> with a third choice;
placing a suitable top-most pair of guards $z=(z_1,z_2)$,
$z_1\in\mathcal{L}$ and $z_2\in\mathcal{R}$,
such that again no “unguarded gap” remains below $(z_1,z_2)$.
Figure <ref> features a funnel in which placing such a pair
of guards $(z_1=l_4,\>z_2=r_4)$ may be strictly better than using any two
consecutive steps of Algorithm <ref>.
On the other hand, we can show that there is no better possibility than one of these three considered steps.
Within the scope of Algorithm <ref> (cf. line <ref>),
we extend the definition range of $\upseg(\cdot)$
to include all boundary points of $\mathcal{L}$ and $\mathcal{R}$, as follows.
If $p$ is an internal point of $\lseg{l_i}{l_{i+1}}$, then we set
If $p'$ is an internal point of $\lseg{r_j}{r_{j+1}}$, then we set

A funnel $\FF$ with concave chains $\mathcal{L}=(l_1, l_2,
\ldots, l_k)$ and $\mathcal{R}=(r_1, \ldots, r_m)$.
A minimum vertex set guarding all the points of $\FF$.
Initialize an auxiliary digraph $G$ with two dummy vertices $x$ and $y$,

Initialize $\ES{S} \gets \{x\}$

$\ES{S}$ is not empty

Choose an arbitrary $t \in \ES{S}$, and remove $t$ from $\ES{S}$
Let $s=\upseg(t)$
*$s$ is a segment or a $\vee$-shape
Let $i'$ and $j'$ be defined for $s$ as in Algorithm <ref>

Let $q$ and $p$ be the ends of $s$ on $\mathcal{L}$ and $\mathcal{R}$, respectively
Let $i''$ and $j''$ be the largest indices such that

*[f]then $l_{i''}$ and $r_{j''}$ together can see whole $s$

Include the vertices $l_{i'}$, $r_{j'}$ and $(l_{i''},r_{j''})$ in $G$

Add the directed edge $(t,z)$ to $G$, and

$\upseg(z)$ includes the apex $l_k=r_m$
Add the directed edge $(z,y)$ to $G$ of weight $0$

(*[f]more guards are needed above $z$)
$\ES{S}\gets \ES{S}\cup\{z\}$

Enumerate a shortest weighted path from $x$ to $y$ in $G$
Output the shortest path vertices without $x$ and $y$,
but considering the possible guard pairs, as the required guard set

Optimum vertex-to-point guarding of funnels.

Algorithm <ref> runs in polynomial time, and it outputs
a feasible guard set of minimum size guarding all the points of a funnel $\FF$.

Proving polynomial runtime is analogous to Lemma <ref>,
only now obtaining a quadratic worst-scenario bound.
Likewise the proof of feasibility of the obtained solution is analogous to
the previous proof.
We only need to observe the following new claim:
if $i''$and $j''$ are defined as on line <ref> of
Algorithm <ref>, then $l_{i''}$ and $r_{j''}$ together
can see whole $s$ and the strip of $\FF$ from $s$ till
The crucial part is to prove optimality.

Having two guard sets $A,B\subseteq V(F)$, we say that $A$ covers $B$ if there is an injection $c:A\to B$ such that, for each $a\in A$,
the guard $c(a)$ is on the same (left or right) chain of $\FF$ as $a$ and not higher than $a$.
Let $G$ be the digraph constructed by Algorithm <ref> on $\FF$.
Note that the weight of any $x$–$y$ path in $G$ equals the number of guards placed along it.
Hence, together with claimed feasibility of the computed solution, it is enough to prove:

* For every feasible vertex guard set $D$ of $\FF$,
there exists a feasible guard set $A$ which covers $D$, and
$A$ has a corresponding directed $x$–$y$ path in the graph $G$
of Algorithm <ref>.

Let $A$ be any feasible guard set of $\FF$ which covers given $D$,
and such that $A$ is maximal w.r.t. the cover relation.
Let $\Pi$ be a maximal directed path in $G$, starting from $x$, such that the set of guards $B_P$ listed in the vertices of $\Pi$ (without $x$)
satisfies $B_P\subseteq A$.
Obviously, we aim to show that $\Pi$ ends in $y$.
Suppose not (it may even be that $\Pi$ is a single vertex $x$ and $B_P=\emptyset$).
Let $t$ be the last vertex of $\Pi$ and denote by $s=\upseg(t)$ and let $q$ and $p$ be the ends of $s$ on $\mathcal{L}$ and $\mathcal{R}$,
respectively, as in the algorithm.

Let $A'=A\setminus B_P\not=\emptyset$.
Then $s$ has to be guarded from $A'$ (while the whole part of $\FF$ below $s$ is already guarded by $B_P$ by feasibility of the algorithm).
Let $i,j$ be such that $l_i\in A'\cap\mathcal{L}$ and $r_j\in A'\cap\mathcal{R}$ are the lowest guards on the left and right chain.
Assume, up to symmetry, that $l_i$ can see whole $s$.
By our maximal choice of $A$ we have that no vertex on $\mathcal{L}$ above $l_i$ can see whole $s$,
and so the digraph $G$ contains an edge from $t$ to $l_i$ (line <ref> of Algorithm <ref>),
which contradicts maximality of the path $\Pi$.

Otherwise, neither of $l_i$, $r_j$ can see whole $s$,
and so $l_i$ sees the end $p$ and $r_j$ sees the end $q$.
Consequently, $l_{i}$ is strictly below $\upseg(p)$ and
$r_{j}$ strictly below $\upseg(q)$, and they are topmost such vertices
again by our maximal choice of $A$.
Hence the digraph $G$ contains an edge from $t$ to $(l_i,r_j)$,
as previously, which is again a contradiction concluding the proof.

Lastly, we establish that the difference between Algorithms <ref> and <ref> cannot be larger than $1$ guard,
because we would like to use the simpler Algorithm <ref> instead of the latter one in subsequent applications.

Let $G^1$ with the source $x^1$ be the auxiliary graph produced by Algorithm <ref>,
and $G^2$ with the source $x^2$ be the one produced by Algorithm <ref>.
We can prove the following detailed statement by induction on $i\geq0$:

* Let $P^2=(x^2=x^2_0,x^2_1,\ldots,x^2_i)$ be any directed path in $G^2$
of weight $k$, let $Q^2$ denote the set of guards listed in the vertices of $P^2$, and
$L^2=\mathcal{L}\cap Q^2$ and $R^2=\mathcal{R}\cap Q^2$.
Then there exists a directed path $(x^1=x^1_0,x^1_1,\ldots,x^1_k,x^1_{k+1})$ in $G^1$
(of length $k+1$), such that the guard of $x_k$ is at least as high as all the
guards of $L^2$ (if $x_k\in\mathcal{L}$) or of $R^2$ (if
$x_k\in\mathcal{R}$), and the guard of $x_{k+1}$ is strictly higher than all
the guards of $Q^2$.

The guard set produced by Algorithm <ref> is always by at most one
guard larger than the optimum solution produced by Algorithm <ref>.

Let $G^1$ with the source $x^1$ be the auxiliary graph produced by Algorithm <ref>,
and $G^2$ with the source $x^2$ be the one produced by Algorithm <ref>.
We instead prove the following refined statement by induction on $i\geq0$.
Recall the detailed inductive statement we are going to prove now:

* Let $\Pi^2=(x^2=x^2_0,x^2_1,\ldots,x^2_i)$ be any directed path in $G^2$
of weight $k$, let $Q^2$ denote the set of guards listed in the vertices of $P^2$, and
$L^2=\mathcal{L}\cap Q^2$ and $R^2=\mathcal{R}\cap Q^2$.
Then there exists a directed path $(x^1=x^1_0,x^1_1,\ldots,x^1_k,x^1_{k+1})$ in $G^1$
(of length $k+1$), such that the guard of $x_k$ is at least as high as all the
guards of $L^2$ (if $x_k\in\mathcal{L}$) or of $R^2$ (if
$x_k\in\mathbb{R}$), and the guard of $x_{k+1}$ is strictly higher than all
the guards of $Q^2$.

The claim is trivial for $i=0$, and so we assume that $i\geq1$ and the claim
holds for the shorter path ${\Pi^2}'=(x^2=x^2_0,x^2_1,\ldots,x^2_{i-1})$ of
weight $k'$ in $G^2$, hence providing us with a path
$(x^1=x^1_0,x^1_1,\ldots,x^1_{k'},x^1_{k'+1})$ in $G^1$.
If $k=k'+1$ (i.e., $x^2_i$ represents a single guard),
Algorithm <ref> can “duplicate” the move, hence making
$x^2_i$ or a higher vertex $x^2_{i'}$ on the same chain
an outneighbour of $x^1_{k'+1}$ in $G^1$.
Then we set $x^1_{k'+2}=x^1_{k+1}=x^2_{i'}$ and we are done.

If $k=k'+2$ (i.e., $x^2_i$ represents a pair of guards $z_1,z_2$),
we proceed as follows.
Up to symmetry, assume $x^1_{k'+1}\in\mathcal{L}$
and $z_1\in\mathcal{L}$, $z_2\in\mathcal{R}$.
By the induction assumption, we know that $x^1_{k'+1}$ is strictly higher
(on $\mathcal{L}$) than the guards from $L^2\setminus\{z_1\}$.
We choose $x^1_k$ as the outneighbour of $x^1_{k'+1}$ in $G^1$ that lies on
$\mathcal{R}$, and $x^1_{k+1}$ as the outneighbour of $x^1_{k}$ in
$G^1$ that lies back on $\mathcal{L}$.
From Algorithm <ref> (line <ref>)
it follows that $z_2$ sees $x^1_{k'+1}$, and so $x^1_k$ is at least as high
on $\mathcal{R}$ as $z_2$.
Consequently, $x^1_{k+1}$ lies on $\mathcal{L}$ strictly higher than $z_1$
(which sees the highest guard from $R^2\setminus\{z_2\}$), and we are again done.

§.§ Conflict-free chromatic guarding of a funnel

In this section, we continue to study funnels.
To obtain a conflict-free colored solution, we will simply
consider the guards chosen by Algorithm <ref> in the ascending
order of their vertical coordinates, and color them in the ruler sequence,
(e.g., [65]) in which the $i^{th}$ term is the exponent of the largest power of $2$ that divides $2i$.

(The first few terms are $1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1\dots$.)

So, if Algorithm <ref> gives $m$ guards, then our approach
will use about $\log m$ colors.

Our aim is to show that this is always very close to the optimum, by giving a lower bound
on the number of necessary colors of order $\log m-O(1)$.
To achieve this, we study the following two sets of guards for a given funnel $\FF$:

* The minimal guard set $A$ computed by Algorithm <ref> on $\FF$
(which is overall nearly optimal by Corollary <ref>);
if this is not unique, then we fix any such $A$.

* A guard set $D$ which achieves the minimum number of colors for
conflict-free guarding; note that $D$ may be much larger than $A$ since it
is the number of colors which matters.

On a high level, we are going to show that the coloring of $D$
must (somehow) copy the ruler sequence on $A$.
For that we will recursively bisect our funnel into smaller “layers”,
gaining one unique color with each bisection.

Analogous to the upper tangent, we define the lower tangent
of a vertex $l_i\in\mathcal{L}$, denote by $\lowtan(l_i)$,
as the ray whose origin is $l_i$ and which passes through $r_j\in\mathcal{R}$
such that $r_j$ is the lowest vertex on $\mathcal{R}$ seeing $l_i$.
Note that $\lowtan(l_i)$ may intersect $\mathcal{R}$ in $r_j$ alone or in a
segment from $r_j$ up.
Let $\lowseg(l_i):=\lseg{l_i}{r_j}$.
The definition of $\lowtan()$ and $\lowseg()$ for vertices of $\mathcal{R}$ is

We now give a definition of “layers” of a funnel which is crucial for our proof.

[yscale=0.75, xscale=1.2]

every node=[draw, shape=circle, fill=black, minimum size=2.5pt,inner sep=0pt];
(1) at (-5,0) ;
(2) at (-3.9, 0.1) ;
(3) at (-3.46, 0.2) ;
(4) at (-2.97, 0.32) ;
(5) at (-2.62, 0.43) ;
(6) at (-2.53, 0.46) ;
(7) at (-2.1, 0.7) ;
(8) at (-1.65, 0.96) ;
(9) at (-1.53, 1.04) ;
(10) at (-1.03, 1.54) ;
(11) at (-0.66, 2.02) ;
(12) at (-0.62, 2.12) ;
[fill=red,minimum size=4pt, label=left:$a_3$] (13) at (-0.32, 3.08) ;
(14) at (-0.19, 3.7) ;
(15) at (-0.14, 4.07) ;
[label=left:$q\>$, fill=white,thick,minimum size=4pt] (16) at (-0.03, 5.54) ;
(17) at (0.03, 8) ;
[fill=red,minimum size=4pt, label=right:$\,a_4$] (18) at (0.26, 6.51) ;
(19) at (0.67, 4.09) ;
(20) at (0.82, 3.42) ;
(21) at (0.99, 2.79) ;
(22) at (1.24, 2.23) ;
(23) at (1.41, 1.92) ;
(24) at (1.6, 1.68) ;
(25) at (1.8, 1.43) ;
(26) at (2.05, 1.16) ;
(27) at (2.23, 0.97) ;
[fill=red,minimum size=4pt, label=above:$a_2$] (28) at (2.56, 0.71) ;
(29) at (2.83, 0.57) ;
(30) at (3.19, 0.42) ;
(31) at (3.94, 0.21) ;
(32) at (4.33, 0.11) ;
(33a) at (4.67, 0.04) ;
(33b) at (4.8, 0.03) ;
(33) at (5, 0) ;
ıin 1,...,32

[thick] (ı)–(ȷ);

[thick] (32)–(33)–(1);

[fill=red,minimum size=4pt,thick, label=above:$\!\!\!a_1=p\!\!\!$] (1g) at (-4.8,0.02) ;
(1') at (2.7,0.62);
(16') at (2.03, 0);
(1int) at (2.6,0.62);
(16int) at (2.02,0);
[dashed, thick] (1g)–(1');
[dashed, thick] (16)–(21);
[dotted, thick] (21)–(16');
[dotted, thick] (2)–(32);
[opacity=0.3,gray] (2) – (32) – (1') – (2);
[opacity=0.5,green] (1'.center)–(2.center)–(3.center)–(4.center)–(5.center)–(6.center)–(7.center)–(8.center)–(9.center)–(10.center)–(11.center)–(12.center)–(13.center)–(14.center)–(15.center)–(16.center)–(21.center)–(22.center)–(23.center)–(24.center)–(25.center)–(26.center)–(27.center)–(28.center)–(29.center)–(1int)–(1.center);
[fill=white, inner sep=0.5pt] at (1.82,0.55) $o$;

An example of a $2$ -interval $Q$ of a funnel (filled green and
bounded by $s_1=\upseg(p)$ and $s_2=\lowseg(q)$).
The red vertices $a_1=p,a_2,a_3,a_4$ are the guards computed
by Algorithm <ref>, and $a_2,a_3$ belong to
the interval $Q$.
Note that $p$ and $q$ by definition do not belong to $Q$.
The shadow of $Q$ (filled light gray) is
bounded from below by the bottom dotted line, and the
inner point $o$ is the so-called observer of $Q$
(seeing all vertices of $Q$ and, possibly, some vertices
in the shadow).

Let $\FF$ be a funnel with the
chains $\mathcal{L}=(l_1, l_2,
\ldots, l_k)$ and $\mathcal{R}=(r_1, r_2, \ldots, r_m)$,
and $A$ be the fixed guard set $A$ computed by Algorithm <ref> on $\FF$.
Let $s_1$ be the base of $\FF$, or $s_1=\upseg(p)$ for some vertex $p$
of $\FF$ (where $p$ is not the apex or its neighbour).
Let $s_2$ be the apex of $\FF$, or $s_2=\lowseg(q)$ for some vertex $q$
of $\FF$ (where $q$ is not in the base of $\FF$).
Assume that $s_2$ is above $s_1$ within $\FF$.
Then the region $Q$ of $\FF$ bounded from below by $s_1$ and from above by
$s_2$, excluding $q$ itself, is called an interval of $\FF$.
Moreover, $Q$ is called a $t$-interval of $\FF$ if $Q$ contains at least
$t$ of the guards of $A$.
See Figure <ref>.

Having an interval $Q$ of the funnel $\FF$, bounded from below by $s_1$,
we define the shadow of $Q$ as follows.
If $s_1=\upseg(l_i)$ ($s_1=\upseg(r_j)$), then the shadow consists of the
region of $\FF$ between $s_1$ and $\lowseg(l_{i+1})$
(between $s_1$ and $\lowseg(r_{j+1})$, respectively).
If $s_1$ is the base, then the shadow is empty.

If $Q$ is a $13$-interval of the funnel $\FF$, then there exists a point
in $Q$ which is not visible from any vertex of $\FF$ outside of $Q$.

By definition, a $13$-interval has thirteen guards from $A$ in it. By
the pigeon-hole principle, at least seven of these guards are on the same chain.
Without the loss of generality, let these seven guards lie on the left chain $\mathcal{L}$ of $\FF$.
Let us denote these guards by $a$, $b$, $c$, $d$, $e$, $f$ and $g$ in the bottom-up order, respectively.
We show that the guard $d$ is not seen by any viewer outside of the $13$-interval.

Suppose that $d$ can be seen by a vertex of $\mathcal{R}$ which lies below $\uptan(a) \cap \mathcal{R}$.
This means that the vertex of $\mathcal{R}$ immediately below $\uptan(a) \cap \mathcal{R}$
(say, denoted by $x$) also sees $d$.

Since $x$ is below $\uptan(a) \cap \mathcal{R}$, $x$ sees all vertices of $\mathcal{L}$ between $b$ and $d$,
including both $b$ and $d$.
Additionally, if $b$ is not the immediate neighbour of $a$ on $\mathcal{L}$,
then $x$ sees the vertex of $\mathcal{L}$ immediately below $b$ as well.
Thus, $x$ sees all points seen by $b$ or $c$ on $\mathcal{L}$.

Since $x$ sees $d$, all points of $\mathcal{R}$ that are seen by $b$ or $c$ and lie above $x$, are also seen by $d$.
Since $x$ lies below $\uptan(a) \cap \mathcal{R}$, $a$ sees all points of $\mathcal{R}$
between and including $x$ and $\lotan(a) \cap \mathcal{R}$.
Since $a$ lies below $b$ and $c$ on $\mathcal{L}$, none among $b$ and $c$ can see any vertex below $\lotan(a) \cap \mathcal{R}$.
Thus, $d$ and $a$ see all points seen by $b$ or $c$ on $\mathcal{R}$.

The above arguments show that $a$, $d$ and $x$ together see all the points on the two concave chains seen by $b$ and $c$.
Observe that since $x$ is the vertex immediately below $\uptan(a) \cap \mathcal{R}$, Algorithm <ref>
includes in $G$ either $x$, or a higher vertex $x'$ of $\mathcal{R}$ which sees the points of $\FF$ exclusively seen by $x$.
This means Algorithm <ref> must choose $x$ (or, $x'$) instead of $b$ and $c$ to optimize on the number of
guards. Hence, we have a contradiction, and no vertex below the $13$-interval can see $d$.

Now suppose that $d$ is seen by a vertex $y$ lying above the $13$-interval. Since the $13$-interval contains
two more guards on $\mathcal{L}$ above $d$, the vertex $y$ can certainly not lie on $\mathcal{L}$.
Therefore, $y$ must lie on $\mathcal{R}$
If the upper segment of the $13$-interval is defined
by $\lowseg(v)$, where $v \in \mathcal{R}$, then $d$, $e$, $f$ and $g$ must lie below
$\lowseg(v) \cap \mathcal{L}$.
This means, $\uptan(d) \cap \mathcal{R}$ must lie below $v$. But to see $d$, $y$ must lie below $v$.
This makes $y$ a vertex contained in the $13$-interval. So, $v$ must lie on $\mathcal{L}$.

So, we assume that $v$ lies on $\mathcal{L}$. At the worst case, $v$ can be the guard $f$.
This means, $\uptan(d) \cap \mathcal{R}$ is above $lot(g) \cap \mathcal{R}$, and $y$ lies on the segment
of $\mathcal{R}$ between these two points. But then, by an argument similar to above, $d$, $g$ and $y$ together see
everything that is seen by $d$, $e$, $f$ and $g$, and so Algorithm <ref> would choose only $d$, $g$
and $y$ to get a shortest path in $G$, a contradiction. So, the point $d$ is not visible from any vertex outside of
the $13$-interval.

Our second crucial ingredient is the possibility to “almost privately” see the vertices of an interval
$Q$ from one point as follows.
If $s_2=\lowseg(q)$, then the intersection point of
$\lowtan(q)$ with $s_1$ is called the observer of $Q$.
(Actually, to be precise, we should slightly perturb this position of the
observer $o$ so that the visibility between $o$ and $q$ is blocked.
To keep the presentation simple, we neglect this detail.)
If $s_2$ is the apex, then consider the spine of $\FF$ instead of $\lowtan(q)$.
See again Figure <ref>.

The observer $o$ of an interval $Q$ in a funnel $\FF$
can see all the vertices of $Q$, but $o$ cannot see any vertex of $\FF$
which is not in $Q$ and not in the shadow of $Q$.

Without the loss of generality let $q$ lie on $\mathcal{L}$.
Since the observer $o$ is the intersection point of $\lowtan(q)$ with $s_1$,
$o$ sees all the vertices of $Q$, since all of them lie between
$s_1$ and  $\lowtan(q)$.
Again, since the observer $o$ is the intersection point of $\lowtan(q)$ with $s_1$,
$o$ lies below a vertex on $\lowtan(q) \cap \mathcal{R}$.
Then this vertex must be a blocker between $o$ and any point of $\FF$ above $s_2$.
So, $o$ cannot see any vertex of $\FF$ above $Q$ that is not in $Q$.
Let $s_1 = \uptan(r)$, where without the loss of generality $r$ lies on $\mathcal{L}$.
Then, since $o$ lies on $s_1$, $o$ cannot see any vertex of $\mathcal{L}$ below $r$.
The shadow of $Q$ on $\mathcal{R}$ extends till $\lowtan(r') \cap \mathcal {R}$, where
$r'$ is the vertex of $\mathcal{L}$ immediately above $r$.
But since $o$ lies on $\upseg(r)$, $o$ is above $r'$, and hence cannot see
vertices of $\mathcal{R}$ below $\lowtan(r') \cap \mathcal {R}$.
Hence, $o$ cannot see vertices below the shadow of $Q$.

The last ingredient before the main proof is the notion
of sections of an interval $Q$ of $\FF$.
Let $s_1$ and $s_2$ form the lower and upper boundary of $Q$.
Consider a vertex $l_i\in\mathcal{L}$ of $Q$.
Then the lower section of $Q$ at $l_i$ is the interval of $\FF$ bounded
from below by $s_1$ and from above by $\lowseg(l_i)$.
The upper section of $Q$ at $l_i$ is the interval of $\FF$ bounded
from below by $\upseg(l_i)$ and from above by $s_2$.
Sections of $r_j\in\mathcal{R}$ are defined analogously.

Let $Q$ be a $t$-interval of the funnel $\FF$, and let $Q_1$ and $Q_2$ be its
lower and upper sections at some vertex $p$.
Then $Q_i$, $i=1,2$, is a $t_i$-interval such that $t_1+t_2\geq t-3$.
(In other words, at most $3$ of the $A$-guards in $Q$ are not in $Q_1\cup Q_2$.)

The only vertices of $Q$ which are not included in $Q_1\cup Q_2$ are
$p$ and the vertices of the shadow of $Q_2$.
Suppose, for a contradiction, that those contain (at least) four guards
from $A$; in either such case, we easily contradict minimality of the guard
set $A$ in Algorithm <ref>, by the same argument given in Lemma <ref>.
The Algorithm <ref> simply chooses $p$ and the topmost and bottommost among these (at least) four guards,
thus choosing only three guards instead of four.

Now we are ready to prove the advertised lower bound:

Any conflict-free chromatic guarding of a given funnel
requires at least $\lfloor\log_2(m+3)\rfloor-3$ colors,
where $m$ is the minimum number of guards needed to guard the whole funnel.

We will prove the following claim by induction on $c\geq0$:

* If $Q$ is a $t$-interval in the funnel $\FF$
and $t\geq 16\cdot2^c-3$, then any conflict-free coloring of $\FF$
must use at least $c+1$ colors on the vertices of $Q$ or
of the shadow of $Q$.

In the base $c=0$ of the induction, we have $t\geq16-3=13$.
By Lemma <ref>, some point of $Q$ is not seen from outside,
and so there has to be a colored guard in some vertex of $Q$,
thus giving $c+1=1$ color.

Consider now $c>0$.
The observer $o$ of $Q$ (which sees all the vertices of $Q$)
must see a guard $g$ of a unique color
where $g$ is, by Lemma <ref>,
a vertex of $Q$ or of the shadow of $Q$.
In the first case, we consider $Q_1$ and $Q_2$,
the lower and upper sections of $Q$ at $g$.
By Lemma <ref>, for some $i\in\{1,2\}$,
$Q_i$ is a $t_i$-interval of $\FF$ such that
$t_i\geq (t-3)/2\geq (16\cdot2^c-6)/2=16\cdot2^{c-1}-3$.
In the second case ($g$ is in the shadow of $Q$),
we choose $g'$ as the lowermost vertex of $Q$ on the same chain as $g$,
and take only the upper section $Q_1$ of $Q$ at $g'$.
We continue as in the first case with $i=1$.

By induction assumption for $c-1$, $Q_i$ together with its shadow
carry a set $C$ of at least $c$ colors.
Notice that the shadow of $Q_2$ is included in $Q$,
and the shadow of $Q_1$ coincides with the shadow of $Q$,
moreover, the observer of $Q_1$ sees only a subset of the shadow of $Q$ seen
by the observer $o$ of $Q$.
Since $g$ is not a point of $Q_i$ or its shadow, but our observer
$o$ sees the color $c_g$ of $g$ and all the colors of $C$, we have
$c_g\not\in C$ and hence $C\cup\{c_g\}$ has at least $c+1$ colors, as

Finally, we apply the above claim to $Q=F$.
We have $t\geq m$, and for $t\geq m\geq 16\cdot2^c-3$ we derive that
we need at least $c+1\geq\lfloor\log(m+3)\rfloor-3$ colors for guarding
whole $\FF$.

A funnel $\FF$ with concave chains $\mathcal{L}=(l_1, l_2,
\ldots, l_k)$ and $\mathcal{R}=(r_1, \ldots, r_m)$.
A conflict-free chromatic guard set of $\FF$
using $\leq OPT+4$ colors.
Run Algorithm <ref> to produce
a guard sequence $A=(a_1,a_2,\dots,a_t)\>$ (bottom-up)
Assign colors to members of $A$ according to the ruler sequence;
the vertex $a_i$ gets color $c_i$
where $c_i$ is the largest integer such that $2^{c_i}$ divides $2i$
Output colored guards $A$ as the (approximate) solution

Approximate conflict-free chromatic guarding of a funnel.

Algorithm <ref>, for a given funnel $\FF$,
outputs in polynomial time a conflict-free chromatic guard set $A$,
such that the number of colors used by $A$ is by at most four larger
than the optimum.

Note the following simple property of the ruler sequence:
if $c_i=c_j$ for some $i\not=j$, then $c_{(i+j)/2}>c_i$.
Hence, for any $i,j$, the largest value occurring among colors
$c_i,c_{i+1},\dots,c_{i+j-1}$ is unique.
Since every point of $\FF$ sees a consecutive subsequence of $A$,
this is a feasible conflict-free coloring of the funnel $\FF$.

Let $m$ be the minimum number of guards in $\FF$.
By Corollary <ref>, it is $m+1\geq t=|A|\geq m$.
To prove the approximation guarantee, observe that for $t\leq 2^c-1$,
our sequence $A$ uses $\leq c$ colors.
Conversely, if $t\geq 2^{c-1}$, i.e. $m\geq 2^{c-1}-1$,
then the required number of colors for guarding $\FF$ is
at least $c-1-3=c-4$, and hence our algorithm uses at most $4$ more colors
than the optimum.

§ WEAK-VISIBILITY POLYGONS

§.§ Guarding a weak-visibility polygon

In this section, we give an algorithm to obtain a set of guards to guard a given weak-visibility polygon.
The algorithm is described by Bhattacharya, Ghosh, and Roy in [16].
Note that the mentioned algorithm is not a novel contribution introduced by this thesis, but we describe it nevertheless for the sake of completeness.

Given the graph $G = (V, E)$ of a weak visibility polygon $\WW$, let $\mathit{SPT}(u)$ denote the shortest path tree of $u \in V$.
Moreover, let $p_u(v)$ denote the parent of $v$ in $\textit{SPT}(u)$, and let $\partial(u,v)$ denote the clockwise boundary of $\WW$ from a vertex $u$ to another vertex $v$.
Analogously, let $\partial'(u,v)$ denote the counterclockwise order.

We start by describing the algorithm (Algorithm 2.1 in [16]) to obtain a guard set for vertex-to-vertex guarding of $\WW$.
The idea of this algorithm is to find a subset $A$ of vertices, such that the guards set of $A$ sees every vertex in $\WW$.
Thus, instead of processing the whole polygon, the algorithm works only on a subset.
The following algorithm describes how $A$ and the guard set of $A$ is chosen.

Computing a guard set $\Gamma_A$ for sove vertices of a given weak-visibility polygon $\WW$

Compute  $\textit{SPT}(u)$ and  $\textit{SPT}(v)$
Initialize all vertices of $\WW$ as unmarked
Initialize $A \gets \emptyset$, $\Gamma_A \gets \emptyset$, and $z \gets u$

$z \neq v$
$z \gets$ the vertex next to $z$ in clockwise order on $\partial(u,v)$
$z$ is not marked

$A \gets A \cup \{z\}$
$\Gamma_A \gets \Gamma_A \cup \{ p_u(z), p_v(z)\}$
Place guards on $p_u(z)$ and $p_v(z)$
Mark all vertices of $\WW$ that are visible from $p_u(z)$ and $p_v(z)$.

In the light of the algorithm given above, the authors describe Algorithm <ref> (Algorithm 2.2 in [16]) which returns a set of guards that guard every vertex in a given weak-visibility polygon.

The input for this algorithm is a weak-visibility polygon $\WW$ with the common edge $uv$.
In short, the algorithm starts with a vertex $z$ is chosen (which is initially $u$), and then traverses all the vertices in the clockwise order from $z$, performing an action with respect to the property of $z$.
The process goes on until the vertex $v$ is reached.

Computing a guard set $\Gamma_B$ for all the vertices of a given weak-visibility polygon $\WW$

Compute  $\textit{SPT}(u)$ and  $\textit{SPT}(v)$
Initialize all the vertices of $\WW$ as unmarked
Initialize $B \gets \emptyset$, $\Gamma_B \gets \emptyset$, and $z \gets su$
there exists an unmarked vertex in $\WW$
$z \gets $ the first unmarked vertex on $\partial(u,v)$ in clockwise order from $z$
every unmarked vertex of $\partial(z,p_v(z))$ is visible from $p_u(z)$ or $p_v(z)$
$B \gets B \cup \{z\}$ and $\Gamma_B \gets \Gamma_B \cup \{p_u(z), p_v(z)\}$
Mark all vertices of $\WW$ that become visible from $p_u(z)$ or $p_v(z)$
$z \gets p_v(z)$

$z' \gets$ the first unmarked vertex on $\partial(z,v)$ in clockwise order
every unmarked vertex of $\partial(p_u(z'),z')$ is visible from $p_u(z')$ or $p_v(z')$
$z\gets z'$ and $z'\gets$ the first unmarked vertex on $\partial(z',v)$ in clockwise order

$w \gets z$
there exists an unmarked vertex on $\partial(u,z)$
$B \gets B \cup \{z\}$ and $\Gamma_B \gets \Gamma_B \cup \{p_u(z), p_v(z)\}$
Mark all vertices of $\WW$ that become visible from $p_u(w)$ or $p_v(w)$
$w \gets$ the first unmarked vertex on $\partial'(z,u)$ in counterclockwise order

§.§ Conflict-free chromatic guarding of a weak-visibility polygon

In this section, we extend the scope of the studied problem of vertex-to-point
conflict-free chromatic guarding from funnels to weak visibility polygons.
We will establish an $O(\log^2 n)$ upper bound for the number of colors
of vertex-guards on $n$-vertex weak-visibility polygons, and give the
corresponding polynomial time algorithm.

every node=[draw, shape=circle, minimum size=4pt,inner sep=0pt];
every path=[thin, fill=none];
[fill=magenta!15!white,draw=none] (0,0)–(6,0.9)–(7.9,2)–(15,8.5)–(15,11.5)–(14.5,13)–(25,1.5)–(31,0)–(0,0);
[fill=black,label=150:$u\,$](A) at (0,0) ;
(B) at (6,0.9) ;
(BB) at (7.9,2) ;
(C) at (8,6) ;
(D) at (7,8) ;
[fill=orange](E) at (4.3,9) ;
[fill=red](F) at (5,11.5) ;
(G) at (7.8,9.5) ;
(H) at (11,8) ;
(I) at (15,8.5) ;
(J) at (15,11.5) ;
[fill=magenta](K) at (14.5,13) ;
[fill=purple](L) at (16.5,12) ;
[fill=blue](M) at (18,13) ;
(N) at (19,10) ;
(O) at (19.5,9) ;
(P) at (23,8) ;
(Q) at (24,10.5) ;
[fill=cyan](R) at (24.2,12) ;
[fill=green](S) at (26,11) ;
[fill=green!60!black](T) at (31,10) ;
(V) at (28.6,8) ;
(W) at (27.5,6) ;
(X) at (25,1.5) ;
[fill=black,label=30:$\,v$](Y) at (31,0) ;

every path=[very thick,dotted];
[orange] (A)–(B)–(BB)–(C)–(D)–(E)–(X)–(Y);
[red] (A)–(B)–(BB)–(C)–(D)–(F)–(G)–(X)–(Y);
[magenta] (A)–(B)–(BB)–(I)–(J)–(K)–(X)–(Y);
[purple] (A)–(B)–(BB)–(I)–(L)–(X)–(Y);
[blue] (A)–(B)–(BB)–(I)–(M)–(N)–(O)–(X)–(Y);
[cyan] (A)–(B)–(P)–(Q)–(R)–(X)–(Y);
[green] (A)–(B)–(P)–(S)–(X)–(Y);
[green!60!black] (A)–(B)–(T)–(V)–(W)–(X)–(Y);

A weak visibility polygon $\WW$ on the base edge $uv$, and
its collection of $8$ max funnels ordered from left to right.
These max funnels are depicted by thick dotted lines, which
are colored from orange on the left to green on the right
(the apex vertex of each max funnel is colored the same as the funnel chains).
Note that the left-most orange funnel is degenerate, i.e.
having its two apex edges collinear.
Moreover, the third (pink) max funnel from the left is
emphasised as the filled region of $\WW$.

Consider a given weak visibility polygon $\WW$ on the base edge $uv$.
Each vertex $w$ of $\WW$ (other than $u,v$) is visible from some point of the segment $\lseg uv$.
Consequently, for this $w$ one can always find a funnel $\FF \subseteq W$ with the base $uv$
and the apex $w$ (such that $V(F)\subseteq V(W)$).
The chains of this funnel $\FF$ are simply the geometric shortest paths inside $\WW$
from $w$ to $u$ and $v$, respectively.
The union of these funnels covers all vertices of $\WW$, and we consider the maximal
ones of them by inclusion – the max funnels of $\WW$ – ordered from left to right.
See Figure <ref>.
Note that, as illustrated in the picture, some max funnels may be degenerate,
which means that their two edges incident with the apex vertex are collinear.

Our algorithm (and the corresponding upper bound)
is based on the following two rather simple observations:

* In each of the max funnels, we assign colors independently in the
logarithmic ruler sequence.
While doing so, we “wastefully” place guards at all vertices
of both chains except the apex (which makes arguments easier).

* In order to prevent conflicts for points seeing guards from
several funnels, we use generally different sets of colors for different
max funnels.
We distribute the color sets to the max funnels again according to the
ruler sequence, from left to right,
which requires only $O(\log n)$ different color sets.
We use the highest ruler sequence value to determine which color set
applies to vertices which belong to several max funnels.

See Algorithm <ref> for details.

Let the ordered set of max funnels (possibly degenerate) of $\WW$ be $\FF = \{F_1, F_2, \ldots, F_m \}$
in the order of their apices occurring on the clockwise boundary of $\WW$ from $u$ to $v$.
Then, as already mentioned, every vertex of $\WW$ belongs to one or more funnels of $\FF$.
Observe that $u$ and $v$ belong to all funnels of $\FF$.
Furthermore, for $F_i \in \FF$ with the apex vertex $a_i$, the point set $W\setminus F_i$
is the union of internally-disjoint polygons such that some of them are to
the left of $F_i$ (those having their vertices between $u$ and $a_i$
in the clockwise order) and the others to the right of $F_i$.
Observe that, for $F_j \in \FF$, we have $j<i$ if and only if $F_j\setminus F_i$
is all to the left of $F_i$.

Computing a vertex-to-point conflict-free chromatic guarding of
a weak visibility polygon using $O(\log^2n)$ colors.

A weak visibility polygon $\WW$, weakly visible from the base edge $uv$.
A V2P conflict-free chromatic guarding of $\WW$ using $O(\log^2 n)$
colors, such that no guard is placed at any apex vertex of a max funnel of $\WW$.

Construct the (geom.) shortest path trees $T_u$ and $T_v$ of $\WW$ from $u$ and $v$
Identify the common leaves of $T_u$ and $T_v$ as the apices of max funnels,
and order them into a set $\FF = \{ F_1, F_2, \ldots, F_m \}$ from left to
right, where $m\leq n$

For $\ell=1+\lfloor\log m\rfloor$,
consider $\ell$ color sets $C_1, C_2, \ldots, C_{\ell}$ of $2\log n$ colors
each, i.e., let $C_i=C^l_i\cup C^r_i$ and all these sets be pairwise
disjoint of cardinality $\log n$

max funnel $F_i\in \FF$
Assign color set $C_j$ to $F_i$, where $j$ is the largest power of $2$ dividing $2i$
*indices $j$ of the assigned sets $C_j$ form the ruler sequ.

vertex $w$ of $\WW$

Associate $w$ with the max funnel that was assigned color set $C_j$ of
the highest index $j$ (among the max funnels containing $w$, this is unique)

max funnel $F_i\in \FF$
color all vertices of the left chain of $F_i$ that are
associated with $F_i$, except the apex, by the ruler sequence
using the color set $C^l_j$ assigned to $F_i$
color the same way the right chain of $F_i$ using the color set $C^r_j$

colored $\WW$

We have the following lemma on $\WW$ and $\FF$.

Consider a weak visibility polygon $\WW$, and its max funnel $F_i \in \FF$.
Assume that an observer $p\in W\setminus F_i$ is to the left of $F_i$ in
$\WW$, and that $x\in W\setminus F_i$ is a point of $\WW$ to the right of $F_i$
such that $p$ sees $x$.
Then $p$ sees at least one vertex of $\WW$ belonging to $F_i$ except the apex.

Note that while it is immediate that the line of sight between $p$ and $x$
must cross both chains of the funnel $F_i$, this fact alone does not imply that
there is a vertex of $F_i$ visible from $p$.

By the definition, $p$ sees a point $b\in\overline{uv}$ on the base of $\WW$.
Consider the ray $\overrightarrow{pb}$ and rotate it counterclockwise until
it first time hits a vertex $c$ on the right chain of $F_i$.
If $p$ sees $c$, then we are done.
Otherwise, the line of sight $\overline{pc}$ is blocked by a point
$y\in\overline{pc}$ such that $y$ is outside of $\WW$, and hence to the left of $F_i$, too.
Let $L_i$ be the point set of the left chain of $F_i$.

Now, both segments $\overline{pb}$ and $\overline{px}$ cross the $L_i$,
and the counter-clockwise order of the rays from $p$
is $\overrightarrow{pb}$, $\overrightarrow{pc}$, $\overrightarrow{px}$.
Consequently, the point set
$\overline{pb}\cup\overline{px}\cup L_i$ (which is part of $\WW$)
separates $y$ (which is in the exterior of $\WW$).
This contradicts the fact that $\WW$ is a simple polygon.

Informally, Lemma <ref> shows that the subcollection of max
funnels whose vertices are seen by the observer $p$, forms a consecutive
subsequence of $\FF$, and so precisely one of these funnels visible by $p$
gets the highest color set according to the ruler sequence.
From this color set we then get the unique color guard seen by $p$.

The straightforward proof of correctness of our algorithm follows.

Algorithm <ref> in polynomial time computes a conflict-free
chromatic guarding of a weak visibility polygon using $O(\log^2 n)$ colors.

Clearly, identifying the max funnels and the indexing can be done in $O(n^2)$ time.
We now prove the correctness of the algorithm.

Any given point $p\in W$ always sees a unique color within any single funnel $F_i \in \FF$,
if at least some vertex of $F_i$ is seen from $p$;
in fact one such unique color left the left or/and one from the right chain
of this funnel (and the color sets of the left and right chains are disjoint).
This is because $p$ always sees a consecutive section of the left or
right chain of $F_i$, regardless of whether $p$ is inside or outside
of $F_i$, and we use the ruler sequence colors on each chain.
However, $p$ may see vertices associated with two or more max funnels assigned the same color set
by Algorithm <ref> (line <ref>).

Suppose the latter; that the point $p$ sees vertices associated with
two distinct max funnels $F_i,F_j \in \FF$ assigned the same color set.
Let $k$, $i<k<j$, be such that $F_k$ is assigned the highest color
set within the ruler subsequence from $i$ to $j$ ($k$ is unique).
If $p\in F_k$, then $p$ sees a unique color guard from those on $F_k$.
Otherwise, up to symmetry, $p$ is to the left of $F_k$ and $p$ sees
a vertex associated with $F_j$ which is to the right of $F_k$.
We have a situation anticipated by Lemma <ref>, and
so $p$ sees some vertex of $F_k$.
Then again, $p$ gets a unique color guard from those on $F_k$.

CHAPTER: GENERAL POLYGONS

§ SUMMARY OF THE CHAPTER

In this chapter, we consider coloring and guarding simple polygons in general, and further generalize some of the results that were presented in previous chapters. This time, we start with the ordinary proper coloring (defined in Section <ref>)

* Given the visibility graph of a simple polygon, we describe a polynomial-time algorithm to determine whether that graph admits a 4-coloring, and return the coloring if exists (Algorithm <ref>).

* We show that the described algorithm can also be implemented without the representation of the polygon (Section <ref>).

* We give NP-hardness reductions for the problems of proper 5-coloring of simple polygons (Section <ref>), and proper 4-coloring of polygons with holes (Section <ref>).

* We show that the vertex-to-point conflict-free chromatic guarding of a simple polygon can be done in $O (\log^2 n)$ guards, which is a generalization of the upper bound for weak-visibility graphs (Algorithm <ref>).

* We consider also the vertex-to-vertex chromatic guarding and give an NP-hardness reduction for that problem as well (Section <ref>).

§ RELATED WORK

Visibility graphs of polygons have been studied with respect to various theoretical and practical computational problems.
The complexities of several popular optimization problems
have been determined for visibility graphs of polygons.
A geometric variation of the dominating set problem, namely polygon guarding, is one of the most studied problems
in computational geometry and is known as the Art Gallery Problem [95].
It has been studied extensively
for both polygons with and without holes and has been found to be NP-hard in both cases [88, 97].
Besides, given a polygon, computing a maximum independent set is known to be hard, due to Shermer [105],
while computing a maximum clique has been shown to be in polynomial time by Ghosh et al. [63].

A proper vertex colouring of a graph is an assignment of labels or colours to the vertices of
the graph so that no two adjacent vertices have the same colours. Henceforth,
when we say colouring a graph, we refer to proper vertex colouring.
The chromatic number of a graph is defined as the minimum number of colours used in any proper colouring of the graph.
Visibility graph colouring has been studied for various types of visibility graphs.
Kára et al. characterized 3-colourable visibility graphs of point sets and
described a super-polynomial lower bound on the chromatic number with respect to
the clique number of visibility graphs of point sets [85].
Pfender showed that, as for general graphs, the chromatic number of visibility graphs
of point sets is also not upper-bounded by their clique numbers [100].
Diwan and Roy showed that for visibility graphs of point sets, the 5-colouring
problem is NP-hard, but 4-colouring is solvable in polynomial time [42].

The problem of colouring the visibility graphs of given polygons
has been studied in the special context where each internal point of the
polygon is seen by a vertex, whose colour appears exactly
once among the vertices visible to that point [15, 69, 50].
However, little is known on colouring visibility graphs of polygons without such constraints.
Although 3-colouring is NP-hard for general graphs [57], in particular it is rather trivial
to solve it for visibility graphs of polygons in polynomial time using a greedy approach.
Already with $4$ colours the same question has been open so far.

In this chapter, we settle the complexity question of
the general problem of colouring polygonal visibility graphs,
which was declared open in 1995 by Lin and Skiena [89].
We first provide a polynomial-time algorithm to find a $4$-colouring
of a given graph $G$ with the promise that $G$ is the visibility graph of some polygon, if $G$ is indeed $4$-colourable.
Then, we provide a reduction showing that the question of
$k$-colourability of the visibility graph of a given simple polygon
is NP-complete for any $k\geq5$.
We also show that $k$-colourability of visibility graphs of polygons with holes is
NP-complete for any $k\geq4$.
Finally, we use our techniques of reduction to give a very simple proof of the NP-hardness
of independent sets of visibility graphs of simple polygons, which was originally proved by Shermer [105].

§ PROPER COLORING OF A POLYGON VISIBILITY GRAPH

§.§ Polynomial-time algorithm for proper 4-coloring

diamondd/.style = inner sep=1.6pt, diamond,
triangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3,
dtriangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3, rotate=180
every node=[draw, shape=circle, minimum size=3pt, inner sep=2pt];
[fill=blue,triangle] (A) at (-5,0) ;
[fill=red,diamondd] (B) at (-5,3) ;
[fill=yellow] (C) at (2,2) ;
[fill=red,diamondd] (D) at (9,3) ;
[fill=blue,triangle] (E) at (9,0) ;
[fill=green] (F) at (2,1) ;

[thick] (A)–(B)–(C)–(D)–(E)–(F)–(A);

A visibility graph that is without a $K_5$, non planar but is 4-colorable.

In this section, we study the algorithmic question of $4$-colorability of the
visibility graph of a given polygon.
The full structure of $4$-colorable visibility graphs is not yet known
and it seems to be non-trivial.
For instance, if a visibility graph is planar, it is $4$-colorable by the 4-color theorem [109].
Though, if such a graph contains $K_5$, then it is neither planar nor $4$-colorable,
but a visibility graph not containing any $K_5$ may be non-planar yet $4$-colorable
(See Figure <ref>).

The related algorithmic problem of 3-coloring visibility graphs is rather
easy to resolve as follows.
Every simple polygon can be triangulated and, in such a triangulation,
every non-boundary edge is contained in two triangles.
One can then proceed greedily edge by edge:
Suppose a triangle has already been colored, and it
shares an edge with a triangle that is not fully colored.
Then the two end vertices of the shared edge
uniquely determine the color of the third vertex of the uncolored triangle.
Finally, one checks whether this unique possible coloring is indeed proper.

Our algorithm essentially generalizes the 3-coloring method for 4-coloring.
We first divide the polygon into reduced polygons.
A polygon $\PP$ is called a reduced polygon, if every chord of $\PP$ (i.e., an internal diagonal) is intersected by another chord of $\PP$.
After the division, we find and color in each reduced subpolygon a triangle (a $K_3$ subgraph) with three distinct colors.
Subsequently, whenever we find an uncolored vertex $v$ adjacent to some three
vertices colored with three distinct colors (such as, to an already
colored triangle), we can uniquely color also $v$, by the fourth color.
We will show that we can exhaust all vertices of a reduced subpolygon in this manner.
Furthermore, we check for possible coloring conflicts – since the
coloring process is unique, this suffices to solve $4$-colorability.

Altogether, this will lead to the following theorem.

The 4-colorability problem is solvable in polynomial time for visibility graphs of simple polygons,
and if a 4-coloring exists, then it can be computed in polynomial time from the given input graph (even without a visibility representation).

We first prove that if a reduced polygon is 4-colorable, then the 4-coloring is unique up to
a permutation of colors.
In the coming proof, consider a polygon $\PP$ and its visibility graph $G(V,E)$, embedded on $\PP$.
Hereafter we slightly abuse notation by equating $\PP$ and $G$.
Since we want to 4-color $\PP$, we assume that $G$ has no $K_5$ (or we answer `no').
We denote the clockwise polygonal chain of $\PP$ from a vertex $u$ to
a vertex $v$ as $\partial(u,v)$ (see Section <ref> for a complete definition).

One can easily see that it is enough to focus on reduced polygons in our proofs.
Indeed, assume an edge $uv$ of $G$ which is a chord of $\PP$ and not crossed
by any other chord.
We can partition $\PP$ into subpolygons $P_1$ and $P_2$, where
$P_1=(u\,\partial(u,v)\,v)$ and $P_2= (v\,\partial(v,u)\,u)$.
Since there is no edge $xy$ of $G$ such that $x$ is in $P_1$ and $y$ is in
$P_2$, the polygons $P_1$ and $P_2$ can be $4$-colored separately
and merged again (provided that $P_1$ and $P_2$ are $4$-colorable).

For a pair of distinct points $x$ and $y$, let $\overline{xy}$ denote the
line segment with the ends $x$ and $y$, and $\overrightarrow{xy}$
denote the half-line (ray) starting in $x$ and passing through $y$.

Let $u$ and $v$ be two vertices of $\PP$.
The shortest path between $u$ and $v$ is a (graph) path from $u$ to
$v$ in $G$ such that the sum of the Euclidean lengths of its edges is minimized.
Such a shortest path between $u$ and $v$ is unique in $\PP$ and is denoted by $\Pi(u,v)$.
Observe that all non-terminal vertices of a shortest path are non-convex [55].
We will assume an implicit ordering of vertices on $\Pi(u,v)$ from $u$ to $v$.
When we say that some vertex $w$ is the first (or last)
vertex on $\Pi(u,v)$ with a certain property, we mean that $w$ precedes
(respectively, succeeds) all other vertices with that property on $\Pi(u,v)$.
For a point $x$, let the right tangent from $x$ to $\Pi(u,v)$
be the ray $\overrightarrow{xy}$ such that $y\in\Pi(u,v)$ (possibly a
segment of $\Pi(u,v)$ belongs to $\overrightarrow{xy}$) and whole
$\Pi(u,v)$ lies in counterclockwise direction from
$\overrightarrow{xy}$, i.e., $\Pi(u,v)$ does not cross $\overrightarrow{xy}$.
A left tangent is defined analogously.

To prove Theorem <ref>, we use the following sequence of lemmas.
In each lemma below, we consider a $K_5$-free reduced polygon $\PP$
and three vertices $\tau_1,\tau_2,\tau_3$ which forms a triangle $T\subseteq G$.
Assume that $T$ is already colored (which is unique up to a permutation of the colors).
Suppose that $i \in V$ is an uncolored vertex, such that an edge incident to $i$ intersects $T$.
Then we have the following lemmas.

diamondd/.style = inner sep=1.6pt, diamond,
triangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3,
dtriangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3, rotate=180
every node=[draw, shape=circle, minimum size=3pt, inner sep=2pt];
[fill=black, label=left:$i$] (vi) at (0,0) ;
[fill=black, label=$j$] (vj) at (9,0) ;
[fill=gray, label=below:$p$] (vp) at (2.5, -0.3) ;
[fill=blue,triangle, label=below:$a$] (va) at (3,-0.4) ;
[fill=red,diamondd, label=below:$\tau_1$] (t1) at (4,-1.2) ;
[fill=yellow, label=below:$\tau_3$] (t3) at (5,-1.2) ;
[fill=red,diamondd, label=below:$t$] (vt) at (6.5,-0.25) ;
[fill=blue,triangle, label=$\tau_2$] (t2) at (4.5,2) ;
[fill=green, label=$u$] (vu) at  (3.8,1) ;

[thick] (vi)–(vp)–(va)–(t1)–(t3);
[dash dot] (t3)  to[out=50,in=200] (vt);
[thick] (vt)–(vj);
[dash dot] (vj) to[out=170,in=320] (t2);
[thick] (t2)–(vu)–(vi);

diamondd/.style = inner sep=1.6pt, diamond,
triangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3,
dtriangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3, rotate=180
every node=[draw, shape=circle, minimum size=3pt, inner sep=2pt];
[fill=black, label=left:$i$] (vi) at (0,0) ;
[fill=black, label=$j$] (vj) at (9,0) ;
[fill=gray, label=below:$p$] (vp) at (2.5, -0.3) ;
[fill=red,diamondd, label=below:$a$] (va) at (3,-0.4) ;
[fill=red,diamondd, label=below:$\tau_1$] (t1) at (4,-1.2) ;
[fill=yellow, label=below:$\tau_3$] (t3) at (5,-1.2) ;
[fill=black, label=below:$t$] (vt) at (6.5,-0.25) ;
[fill=yellow, label=30:$w$] (vw) at (5.3,0.25) ;
[fill=blue,triangle, label=$\tau_2$] (t2) at (4.5,2) ;
[fill=green, label=$u$] (vu) at  (3.8,1) ;

[thick] (vi)–(vp)–(va);
[dash dot] (va) to[out=340,in=120] (t1);
[thick] (t1)–(t3);
[dash dot] (t3)  to[out=80,in=180] (vt);
[thick] (vt)–(vj)–(vw)–(t2)–(vu)–(vi);

[dotted] (vt)–(vw)–(vu);
[->] (vu)–(4.5,1.5);
[->] (vu)–(4.9,1.3);

diamondd/.style = inner sep=1.6pt, diamond,
triangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3,
dtriangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3, rotate=180
every node=[draw, shape=circle, minimum size=3pt, inner sep=2pt];
[fill=black, label=left:$i$] (vi) at (0,0) ;
[fill=black, label=$j$] (vj) at (9,0) ;
[fill=black, label=200:$p$] (vp) at (2.5, -0.3) ;
[fill=red,diamondd, label=250:$a$] (va) at (3,-0.4) ;
[fill=blue,triangle, label=below:$z$] (vz) at (3.4,-0.5) ;
[fill=red,diamondd, label=below:$\tau_1$] (t1) at (4,-1.2) ;
[fill=yellow, label=below:$\tau_3$] (t3) at (5,-1.2) ;
[fill=red,diamondd, label=below:$d$] (vd) at (5.5,-0.7) ;
[fill=gray, label=-30:$s$] (vs) at (5.8,-0.5) ;
[fill=black, label=-30:$t$] (vt) at (6.5,-0.25) ;
[fill=blue,triangle, label=$\tau_2$] (t2) at (4.5,2) ;
[fill=green, label=$u$] (vu) at  (3.8,1) ;

[dash dot] (vz) to[out=340,in=120] (t1);
[thick] (vi)–(vp)–(va);

[thick] (t1)–(t3);
[dash dot] (t3)  to[out=70,in=200] (vd);
[thick] (vd)–(vs);
[dash dot] (vs)  to[out=40,in=180] (vt);
[thick] (vt)–(vj);
[dash dot] (vj)  to[out=170,in=320] (t2);

[dotted] (vt)–(vu);
[->] (vu)–(6.5,1.5);
[->] (vu)–(6.9,1.3);

diamondd/.style = inner sep=1.6pt, diamond,
triangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3,
dtriangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3, rotate=180
every node=[draw, shape=circle, minimum size=3pt, inner sep=2pt];
[fill=black, label=left:$i$] (vi) at (0,0) ;
[fill=black, label=$j$] (vj) at (9,0) ;
[fill=black, label=200:$p$] (vp) at (1, -0.2) ;
[fill=blue,triangle, label=250:$a$] (va) at (2,-0.4) ;
[fill=red,diamondd, label=250:$g$] (vg) at (3,-0.6) ;
[fill=red,diamondd, label=below:$\tau_1$] (t1) at (4,-1.2) ;
[fill=yellow, label=below:$\tau_3$] (t3) at (5,-1.2) ;
[fill=black] (vt) at (6.7,-0.3) ;
[fill=black] (vt') at (6,0.2) ;
[fill=blue,triangle, label=$\tau_2$] (t2) at (4.5,2.3) ;
[fill=green, label=$b$] (vb) at  (4,1.5) ;
[fill=black, label=$q$] (vq) at  (3.2,0.5) ;
[fill=black] (vq') at  (2.7,0.2) ;

[thick] (vi)–(vp)–(va)–(vg);
[thick] (t1)–(t3);
[dash dot] (vg) to[out=340,in=120] (t1);
[dash dot] (t3)  to[out=80,in=190] (vt);
[thick] (vt)–(vj)–(vt')–(t2);
[thick] (t2)–(vb)–(vq)–(vq')–(vi);

Illustration of the proof of Lemma <ref>:
The vertices whose colors shall be uniquely determined next, are
now drawn in gray. Polygonal boundaries containing multiple
vertices not included in the figure are drawn with dashed lines.
(a) $p$ forms a $K_4$ with $a$, $t$ and $u$. (b) $p$ forms a $K_4$ with $a$, $u$ and $w$.
(c) $s$ forms a $K_4$ with $u$, $d$ and $z$. (d) $g$, $q$ and $b$ form a $K_3$.

diamondd/.style = inner sep=1.6pt, diamond,
triangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3,
dtriangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3, rotate=180
every node=[draw, shape=circle, minimum size=3pt, inner sep=2pt];

[dash dot] plot [smooth, tension=1] coordinates (1, -0.1) (1.5,0.1) (2.5,0.3);
[fill=red,diamondd, label=left:$\tau_1$] (t1) at (0,-0.1) ;
[fill=blue,triangle, label=$\tau_2$] (t2) at (0.5, 0.5) ;
[fill=yellow, label=right:$\tau_3$] (t3) at (1, -0.1) ;
[fill=blue,triangle, label=$a$] (va) at (2,0.6) ;
[fill=gray, label=$u$] (vu) at (2.3,0.8) ;
[fill=green, label=$b$] (vb) at (2.9,0.6) ;
[fill=red,diamondd, label=right:$d$] (vd) at (2.9,0.37) ;
[fill=black] (vbl) at  (3.45,0.1) ;
[fill=blue,triangle, label=$i$] (vi) at (3.7,0.6) ;

[thick] (t1)–(t2)–(t3)–(t1);
[thick] (t1)–(vi);
[dash dot, bend right] (t2) to (va);
[dash dot] (vb)–(vi);

The vertex $a$ has an edge incident to one of the vertices of
$a,b,c$, where $a$, $b$ and $c$ lie on the already colored
shortest paths from $\tau_1$ and $\tau_3$ to $i$.

Assume that two vertices $i \in \partial(\tau_1, \tau_2)$ and $j \in \partial(\tau_2, \tau_3)$ see each other, and the edge $ij$
intersects $\tau_1\tau_2$ and $\tau_2 \tau_3$. Then the colors of all vertices on the four paths
$\Pi(\tau_1, i)$, $\Pi(\tau_2, i)$, $\Pi(\tau_2, j)$ and $\Pi(\tau_3, j)$,
including $i,j$
themselves, are uniquely determined by the colors of $T$.

We prove the claim by induction on the four paths.
As the base case, the first vertices of these paths are the vertices
of $T$, which are already assigned different colors.

For the induction step, assume that $\Pi(\tau_1,i)$, $\Pi(\tau_2,i)$,
$\Pi(\tau_2,j)$ and $\Pi(\tau_3,j)$ have been colored till vertices $a$, $b$, $c$ and
$d$ respectively.
Also, their immediate uncolored successors on $\Pi(\tau_1,i)$, $\Pi(\tau_2,i)$,
$\Pi(\tau_2,j)$ and $\Pi(\tau_3,j)$ are $p$, $q$, $r$ and $s$ respectively.
We aim to show that the colors of at least one of $p$, $q$, $r$ and $s$
is uniquely determined by the already colored vertices.

If $p$ does not see $b$ and any predecessor of $b$ on $\Pi(\tau_2,i)$, then
$q$ must see $a$ or some predecessor of $a$ on $\Pi(\tau_1,i)$.
We have the following cases (cf. Figure <ref>).

*Case 1: $p$ sees $b$ or some predecessor of $b$ on $\Pi(\tau_2,i)$.
By definition, $p$ is the immediate successor of $a$ on $\Pi(\tau_1,i)$,
and thus $p$ must see $a$.
The right tangent of $a$ to $\Pi(\tau_2,i)$ lies to the right of the right tangent of $p$ to $\Pi(\tau_2,i)$. So, if the right tangent of $p$ touches $\Pi(\tau_2,i)$ at a vertex $u$, then $a$ sees $u$.
Note that either $u = b$, or $u$ precedes $b$ on $\Pi(\tau_2,i)$. In any case, $u$ is already colored.
Since $p$, $a$ and $\Pi(\tau_3,j)$ lie on the same side of $ij$, and $p$ is nearer
to $ij$ than $a$ is, $p$ and $a$ see a vertex $t$ of $\Pi(\tau_3,j)$.
If $u$ also sees $t$, and $t$ is already colored, then the claim is proved
(Figure <ref>(a)).
So we consider the other two cases, namely, that $u$ does not see $t$, or that $t$ is not yet colored.

Subcase 1.a:  $u$ does not see $t$.

Since $t$ and $u$ lie on different sides of $\overline{ij}$ and of $\overline{\tau_2\tau_3}$,
the edges of some vertex of $\Pi(\tau_2,j)$ must be blocking $u$ and $t$.
Let $w$ be the first vertex of $\Pi(\tau_2,j)$ blocking the visibility between $u$ and $t$.

Then $u$ sees $w$. The vertex $w$ is closer to $\overline{ij}$ than $u$ is.
Also, $w$ lies to the right of $\overrightarrow{au}$ and $\overrightarrow{pu}$,
and to the left of $\overrightarrow{at}$ and $\overrightarrow{pt}$.
Then the only possible segments blocking visibility between $w$ and either $p$ or $a$ can be from $\Pi(\tau_2,i)$.
But all the vertices on $\Pi(\tau_2,i)$ preceding $u$ are farther from $\overline{ij}$ than $u$ is.
So, there can be no such blocker, and $w$ must be visible from both $a$ and $p$ (Figure <ref>(b)).
If $w$ is already colored, then the claim is proved.

Suppose that $w$ is not already colored.
Then consider $r$, which now precedes $w$ on $\Pi(\tau_2,j)$.
The vertices $r$ and $c$ are consecutive on $\Pi(\tau_2,j)$ and hence see each other.

Since $\Pi(\tau_2,j)$ and $\Pi(\tau_1,i)$ are on opposite sides of the edge $ij$, the vertices $c$ and $r$ both see $a$, or some vertex preceding $a$ on $\Pi(\tau_1,i)$. Let $x$ be the last colored vertex
of $\Pi(\tau_1,i)$ seen by both $c$ and $r$.
Let $x$ be the last colored vertex of $\Pi(\tau_1,i)$ seen by both $c$ and $r$.
If $x \neq a$ then let $y$ be the last vertex of $\Pi(\tau_2,i)$ that blocks $c$ from the successor of $y$ on $\Pi(\tau_1,i)$.
Then, $y$ must be visible from $x$, $r$ and $c$.

Since $x$ precedes $a$ on $\Pi(\tau_1,i)$, and $y$ precedes $b$ on $\Pi(\tau_2,i)$, both $x$ and $y$ must already be colored, and thus the color of $r$ is uniquely determined by $T$.
If $x=a$ then since $u$ is on the right tangent of $a$ to $\Pi(\tau_2,i)$, both $c$ and $r$ see $u$,
and thus the color of $r$ is uniquely determined by $T$ in this case as well.

Now we move to the second subcase.

Subcase 1.b: $u$ sees $t$, but $t$ is not yet colored.

Since $u$ sees $t$, $\Pi(\tau_2,j)$ is a concave chain and the edge $\tau_1\tau_3$  exists in $\PP$,
$u$ must see every predecessor of $t$ on $\Pi(\tau_2,j)$.
This means that both $d$ and $s$ see $u$ (Figure <ref>(c)).
Let the right tangent from $d$ touches $\Pi(\tau_1,i)$ in a vertex $y$.
Then $s$ must see $y$, because the last vertices $i$ and $j$ of
the concave chains $\Pi(\tau_1,i)$ and $\Pi(\tau_3,j)$ see each other.
Also, the left tangent of $u$ to $\Pi(\tau_1,i)$ must touch $\Pi(\tau_1,i)$ at a vertex equal to or preceding $y$.
Thus, all three of $s$, $d$ and $u$ see a common vertex $z$ on $\Pi(\tau_1,i)$ which precedes $a$, since $u$ and $t$ see $a$.
Thus, $z$ is already colored, and $u$, $d$ and $z$ form a $K_4$ with $s$, the color of $s$ is uniquely determined by $u$, $d$ and $z$.

*Case 2: $p$ does not see $b$ or any predecessor of $b$ on $\Pi(\tau_2,i)$.

Since $\Pi(\tau_2,i)$ is a concave chain, this means that the tangent drawn from $p$ to $\Pi(\tau_2,i)$ in the direction of $\tau_2$, has whole $\Pi(\tau_2,b)$ to its left (refer to Figure <ref>(d)).
Suppose that $b$ does not see any vertex of $\Pi(\tau_1,a)$.
Since $\Pi(\tau_1,i)$ is also a concave chain, and $\tau_1$ sees $\tau_2$, all segments
blocking visibility between $q$ and $\Pi(\tau_1,a)$ must come from $\Pi(p,i)$, and must include $p$.
But then, the aforementioned tangent drawn from $p$ to $\Pi(\tau_2,i)$
must have at least part of $\Pi(\tau_2,b)$ to the right, which is absurd.

So, $b$ must see $a$ or some other vertex of $\Pi(\tau_1,a)$.
Let $g$ denote the last vertex of $\Pi(\tau_1,i)$ seen by $b$.
Then, $g$ exists, and it belongs to $\Pi(\tau_1,a)$ since $p$ (the successor of $a$) does not see $b$, and $g$ is seen by $q$ (Figure <ref>(d)).
Since the vertex $g$ is on $\Pi(\tau_1,a)$, it is already colored.

Let us now similarly consider a vertex, say $t$ on $\Pi(\tau_2, j)$,
which is seen by both $b$ and $q$.
Suppose that $g$ or another common colored neighbor of $b$ and $q$ sees $t$.
Then we are immediately done if $t$ is colored, or we are in Subcase 1.b if $t$ is uncolored.
Otherwise, some vertex on $\Pi(\tau_3, j)$ blocks all visibilities between $t$
and all the common neighbors of $q$ and $b$.
Then we finish as in Subcase 1.a.

If any vertex $i$ of $\PP$ sees a vertex of $T$ and their visibility edge crosses one of the edges of $T$, then the color of $i$ is uniquely determined by the colors of $T$.

Without loss of generality, suppose that $i$ sees $\tau_1$, and $i\tau_1$ crosses $\tau_2\tau_3$. Then $j=\tau_1$, $\Pi(\tau_2,j) = \tau_2\tau_1$
and $\Pi(\tau_1,j) =\tau_1$, and Lemma <ref> proves the claim.

If a reduced polygon is 4-colorable, then it has a unique 4-coloring up to permutation of colors.

Consider a triangle $T$ in a reduced polygon $\PP$.
If $\PP$ is not just $T$, then at least one edge of $T$ is not a boundary edge of $\PP$.
Without loss of generality, let $\tau_1\tau_2$ be such an edge.

Since $\PP$ is reduced, there must be a vertex $i$ on $\partial(\tau_1, \tau_2)$
such that an edge incident to $i$ crosses $\tau_1 \tau_2$.
By Lemma <ref> and Corollary <ref>, if $\PP$ is 4-colorable, then
all vertices on the paths $\Pi(\tau_1, i)$ and $\Pi(\tau_2, i)$, including $i$ have a 4-coloring uniquely determined by $T$.
In case $\tau_2 \tau_3$ or $\tau_3 \tau_1$ are not boundary edges of $\PP$, we can similarly find $j$ on
$\partial(\tau_2, \tau_3)$ 	and $k$ on $\partial(\tau_3, \tau_1)$ and uniquely 4-color $\Pi(\tau_2, j)$,
$\Pi(\tau_3, j)$, $\Pi(\tau_3, k)$ and $\Pi(\tau_1, k)$.

diamondd/.style = inner sep=1.6pt, diamond,
triangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3,
dtriangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3, rotate=180
every node=[draw, shape=circle, minimum size=3pt, inner sep=2pt];
[fill=red,diamondd, label=left:$t_3$] (t1) at (0,-0.1) ;
[fill=blue,triangle, label=$t_1$] (t2) at (0.5, 0.7) ;
[fill=yellow, label=right:$t_2$] (t3) at (1, -0.1) ;
[fill=blue,triangle, label=$a$] (va) at (1.7,0.53) ;
[fill=gray, label=$u$to 0pt ($z$)] (vu) at (2.1,0.85) ;
[fill=green,dtriangle, label=below:$b$] (vb) at
(2.9,0.55) ;
[fill=yellow, label=right:$w$] (vd) at (2.9,0.45) ;
[fill=blue,triangle, label=$i$] (vi) at (3.7,0.6) ;

[thick] (t2)–(t1)–(t3);
[dash dot] (t2) to[out=340,in=180] (va);
[dash dot] (vb)–(vi);
[dash dot] (t3) to[out=20,in=190] (vi);
every path=[color=cyan];
[thick] (0.4,0.2)–(vi);
[thick] (t2)–(t3);
[thick] (vu)–(vd);

diamondd/.style = inner sep=1.6pt, diamond,
triangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3,
dtriangle/.style = inner sep=1.2pt, regular polygon, regular polygon sides=3, rotate=180
every node=[draw, shape=circle, minimum size=3pt, inner sep=2pt];
[fill=red,diamondd, label=left:$t_3$] (t1) at (0,-0.1) ;
[fill=blue,triangle, label=$t_1$] (t2) at (0.5, 0.7) ;
[fill=yellow, label=right:$t_2$] (t3) at (1, -0.1) ;
[fill=blue,triangle, label=$a$] (va) at (1.7,0.53) ;
[fill=gray, label=$u$] (vu) at (1.9,0.85) ;
[fill=green,dtriangle, label=below:$b$] (vb) at (2.9,0.55) ;
[fill=yellow, label=below:$c$] (vc) at (1.3,0.06) ;
[fill=red,diamondd, label=below:$d$] (vd) at (3.2,0.5) ;
[fill=white] (vbl) at  (2.7,0) ;
[fill=blue,triangle, label=$i$] (vi) at (3.7,0.6) ;

[thick] (t2)–(t1)–(t3);
[dash dot] (t2) to[out=340,in=180] (va);
[dash dot] (vb)–(vi);
[dash dot] (t3) to[out=50,in=190] (vc);
[dash dot] (vd)–(vi);
every path=[color=cyan];
[thick] (0.4,0.2)–(vi);
[thick] (t2)–(t3);
[thick] (vu)–(vbl);

Illustration of the proof of Theorem <ref>.
Top: an edge incident to $u$ sees a colored vertex on $\Pi(t_2, i)$.
Bottom: an edge incident to $u$ crosses an edge $cd$ of $\Pi(t_2, i)$.
Both cases can be resolved by an application of Lemma
<ref> and Corollary <ref> to the already
colored triangles $abw$ and $abc$, respectively.

Now, all the remaining uncolored vertices of $\PP$ are on polygonal chains of the form
$\partial(a, b)$,
where $a$ and $b$ are two consecutive vertices in one of the six paths mentioned above. Furthermore,
no vertex in the polygonal chain $\partial(a, b)$, other than $a$ and $b$, is colored.
Without loss of generality, let $a$ and $b$ be two consecutive vertices on $\Pi(\tau_1, \tau_2)$.
If $a b$ is not a boundary edge of $\PP$, then since $\PP$ is reduced, there must be an
uncolored vertex $u$ in $\partial(a, b)$ such that an edge incident to $u$ crosses $a b$.
This edge is either incident to a vertex of $\Pi(\tau_2, i)$, or crosses an edge of
$\Pi(\tau_2, i)$.
Consider the case where such an edge to a vertex of $\Pi(\tau_2, i)$ exists.
Then consider a vertex $w$ that is closest to $ab$ among all the vertices
of $\Pi(\tau_2, i)$ that see a vertex (say, $z$) of $\partial(a, b)$. Since the edge $wz$ exists,
$w$ cannot be blocked by any vertex of $\Pi(\tau_1, i)$. Due to the choice of $w$, no vertex of
$\Pi(\tau_2, i)$ can block $w$ from $a$ or $b$. So, $w$ sees both $a$ and $b$.
Now consider the case where no vertex of $\partial(a, b)$ sees any vertex of $\Pi(\tau_2, i)$, but some vertex of
$\partial(a, b)$ sees some vertex of $\partial(c, d)$,
where $c$ and $d$ are consecutive points on $\Pi(\tau_2, i)$.
Without loss of generality, assume that $c$ precedes $d$ in $\Pi(\tau_2, i)$. Then $c$ must see both $a$ and $b$ (Figure <ref>),
for otherwise a vertex of $\partial(a, b)$ must have an edge with some
vertex of $\Pi(\tau_2, i)$ acting as a blocker for $c$, contrary to our assumption.
Then, in the above two cases, based on the triangle $a b w$ and $a b c$, respectively,
again Lemma <ref> and Corollary <ref> can be used to
uniquely determine a 4-coloring for $\Pi (a, u)$ and $\Pi(b, u)$.

Now we generalize the above procedure. Let $T_0 = \{T\}$, and let $S_0 = \{
\Pi(\tau_1, i),\Pi(\tau_2, i)\Pi(\tau_2, j), \Pi(\tau_3, j), \Pi(\tau_3, v_k), \Pi(\tau_1, v_k)\}$.
Note that we have assumed that none of the edges of $T$ are boundary edges. If some edges of $T$ are boundary edges then $S_0$ will have less elements.