3SAT

11institutetext: Graz University of Technology, Graz, Austria 11email:
<EMAIL_ADDRESS>22institutetext: Tufts University,
Medford, MA, USA 22email<EMAIL_ADDRESS>33institutetext: The
University of Electro-Communications and RIKEN Center for Advanced
Intelligence Project, Tokyo, Japan 33email<EMAIL_ADDRESS>44institutetext: The University of Sydney, Sydney, Australia 44email:
<EMAIL_ADDRESS>
# Graphs with large total angular resolution††thanks:  This work started
during the Japan-Austria Joint Seminar _Computational Geometry Seminar with
Applications to Sensor Networks_ supported by the Japan Society for the
Promotion of Science (JSPS) and the Austrian Science Fund (FWF) under grant
AJS 399. O.A., I.P., D.P., and B.V. are partially supported by the FWF grants
W1230 (Doctoral Program Discrete Mathematics) and I 3340-N35 (Collaborative
DACH project _Arrangements and Drawings_).

Oswin Aichholzer 11 0000-0002-2364-0583 Matias Korman 22 Yoshio Okamoto 33
0000-0002-9826-7074 Irene Parada 11 0000-0003-3147-0083 Daniel Perz 11
0000-0002-6557-2355 André van Renssen 44 0000-0002-9294-9947 Birgit
Vogtenhuber 11 0000-0002-7166-4467

###### Abstract

The total angular resolution of a straight-line drawing is the minimum angle
between two edges of the drawing. It combines two properties contributing to
the readability of a drawing: the angular resolution, which is the minimum
angle between incident edges, and the crossing resolution, which is the
minimum angle between crossing edges. We consider the total angular resolution
of a graph, which is the maximum total angular resolution of a straight-line
drawing of this graph. We prove that, up to a finite number of well specified
exceptions of constant size, the number of edges of a graph with $n$ vertices
and a total angular resolution greater than $60^{\circ}$ is bounded by $2n-6$.
This bound is tight. In addition, we show that deciding whether a graph has
total angular resolution at least $60^{\circ}$ is -hard.

###### Keywords:

Graph drawing Total angular resolution Angular resolution Crossing resolution
NP-hardness.

##  1 Introduction

The _total angular_ resolution of a drawing $D$, or short
$\operatorname{TAR}(D)$, is the smallest angle occurring in $D$, either
between two edges incident to the same vertex or between two crossing edges.
In other words, $\operatorname{TAR}(D)$ is the minimum of the angular
resolution $\operatorname{AR}(D)$ and the crossing resolution
$\operatorname{CR}(D)$ of the same drawing. Furthermore, the total angular
resolution of a graph $G$ is defined as the maximum of $\operatorname{TAR}(D)$
over all drawings $D$ of $G$. Similarly, the angular resolution and the
crossing resolution of $G$ are the maximum of $\operatorname{AR}(D)$ and
$\operatorname{CR}(D)$, respectively, over all drawings $D$ of $G$. The total
angular resolution of a graph is in general smaller than the minimum of its
crossing resolution and its angular resolution. Note that all drawings
considered in this work are straight-line.

Formann et al. [7] were the first to introduce the angular resolution of
graphs and showed that finding a drawing of a graph with angular resolution at
least $90^{\circ}$ is -hard. Fifteen years later experiments by Huang et al.
[8, 10] showed that the crossing resolution plays a major role in the
readability of drawings. Consequently research in that direction was
intensified. In particular right angle crossing drawings (or short RAC
drawings) were studied [5, 11], and -hardness of the decision version for
right angles was proven [2].

The upper bound for the number of edges of $\alpha{AC}$ drawings (drawings
with crossing resolution $\alpha$) is $\frac{180^{\circ}}{\alpha}(3n-6)$ [6].
For the two special classes of RAC drawings and $60^{\circ}$AC drawings better
upper bounds are known. More precisely, RAC drawings have at most $4n-10$
edges [5] and $\alpha$AC drawings with $\alpha>60^{\circ}$ have at most
$6.5n-20$ edges [1].

Argyriou et al. [3] were the first to study the total angular resolution,
calling it just _total resolution_. They presented drawings of complete and
complete bipartite graphs with asymptotically optimal total angular
resolution. Recently Bekos et al. [4] presented a new algorithm for finding a
drawing of a given graph with high total angular resolution which was
performing superior to earlier algorithms like [3, 9] on the considered test
cases.

##  2 Upper bound on the number of edges

We say a drawing $D$ is planarized if we replace every crossing by a vertex so
that this new vertex splits both crossing edges into two edges. We denote this
planarized drawing by $P(D)$. Furthermore, every edge in $P(D)$ has two sides
and every side is incident to exactly one cell of $D$. Note that both sides of
an edge can be incident to the same cell. We define the size of a cell of a
connected drawing $D$ as the number of sides in $P(D)$ incident to this cell.

In this section we show that for almost all graphs with
$\operatorname{TAR}(G)>60^{\circ}$ the number of edges is bounded by $2n-6$.
We start by showing a bound for the number of edges in a connected drawing $D$
depending on the size of the unbounded cell of $D$.

###### Lemma 1

Let $D$ be a connected drawing with $n\geq 1$ vertices and $m$ edges. If the
unbounded cell of $D$ has size $k$ and $\operatorname{TAR}(D)>60^{\circ}$,
then $m\leq 2n-2-\left\lceil{k}/{2}\right\rceil$.

###### Proof

If at least three edges cross each other in a single point, then there exists
an angle with at most $60^{\circ}$ at this crossing point. Therefore every
crossing is incident to two edges. We planarize the drawing $D$ and get
$n^{\prime}=n+\operatorname{cr}(D)$ and $m^{\prime}=m+2\operatorname{cr}(D)$
where $\operatorname{cr}(D)$ is the number of crossings in $D$, $n^{\prime}$
is the number of vertices of $P(D)$, and $m^{\prime}$ is the number of edges
of $P(D)$. Since we have a planar graph, we can use Euler’s formula to compute
the number $f$ of faces in $P(D)$ as

$\displaystyle f=-n+m+\operatorname{cr}(D)+2.$ (1)

Moreover, every bounded cell of $D$ has at least size $4$, as otherwise $P(D)$
contains a triangle which implies an angle of at most $60^{\circ}$. By
definition, the unbounded cell of $D$ has size $k$ and we obtain the following
inequality

$2m^{\prime}\geq 4(f-1)+k.$ (2)

Combining Equation (1) and Inequality (2) gives ${m\leq
2n-2-\left\lceil{k}/{2}\right\rceil}$. ∎

From Lemma 1 it follows directly that a connected drawing $D$ on $n\geq 3$
vertices and with $\operatorname{TAR}(D)>60^{\circ}$ fulfills $m\leq 2n-4$.

Observation 1, which will be useful to prove Lemma 2, follows from the fact
that the sum of interior angles in a simple polygon is $180^{\circ}(p-2)$.

###### Observation 1

Let $D$ be a plane drawing where the boundary of the unbounded cell is a
simple polygon $P$ with $p>3$ vertices. Let the inner degree of a vertex
$v_{i}$ of $P$ be the number $d^{\prime}_{i}$ of edges incident to $v_{i}$
that lie in the interior of $P$. If $\operatorname{TAR}(D)>60^{\circ}$, then
$\sum_{v_{i}\in V(P)}d^{\prime}_{i}\leq 2p-7$ holds.

###### Lemma 2

Let $D$ be a connected plane drawing on $n\geq 3$ vertices, where $D$ is not a
path on $3$ vertices and not a $4$-gon. If $\operatorname{TAR}(D)>60^{\circ}$,
then $m\leq 2n-5$.

###### Proof

The unbounded cell of $D$ cannot have size $3$, as in this case the convex
hull of the drawing is a triangle and we have $\operatorname{TAR}(D)\leq
60^{\circ}$. If the drawing $D$ has an unbounded cell of size at least $5$ and
$\operatorname{TAR}(D)>60^{\circ}$, then $m\leq 2n-5$ follows directly from
Lemma 1. Otherwise, the unbounded cell of $D$ has size $4$, which, as $D$ is
not a path on $3$ vertices, implies that the boundary of $D$ is a 4-gon $F$.
By Observation 1 and the fact that $D$ is not a 4-cycle, there is precisely
one edge $e$ in the interior of and incident to $F$. Let $D^{\prime}$ be the
drawing we get by deleting all vertices and edges of $F$ and also the edge
$e$. The drawing $D^{\prime}$ is connected and has $n^{\prime}\geq 1$ vertices
and $m^{\prime}$ edges, where $n=n^{\prime}+4$ and $m=m^{\prime}+5$. By Lemma
1 we know that $m^{\prime}\leq 2n^{\prime}-2$ and we derive
$m=m^{\prime}+5\leq 2n^{\prime}-2+5\leq 2n-5$. ∎

Two drawings are _combinatorially equivalent_ if all cells are bounded by the
same edges, all crossing edge pairs are the same, and the order of crossings
along an edge are the same. We can extend Lemma 2 in the following way.

###### Lemma 3

Let $D$ be a connected plane drawing on $n\geq 3$ vertices with
$\operatorname{TAR}(D)>60^{\circ}$. If $D$ is not combinatorially equivalent
to one of the exceptions E1–E9 as listed below and depicted in Fig. 5
(Appendix 0.B), then $m\leq 2n-6$.

  1. _E1_

A tree on at most 4 vertices.

  2. _E2_

An empty $4$-gon.

  3. _E3_

A $4$-gon with one additional vertex connected to one vertex of the $4$-gon.

  4. _E4_

An empty $5$-gon.

  5. _E5_

A $5$-gon with one inner vertex connected to two non-neighboring vertices of
the $5$-gon.

  6. _E6_

A $5$-gon with an edge inside, connected with 3 edges to the 5-gon such that
the 5-gon is partitioned into two empty 4-gons and one empty $5$-gon.

  7. _E7_

A $6$-gon with an additional diagonal between opposite vertices.

  8. _E8_

A $6$-gon with an additional vertex or edge inside, connected with 3 or 4,
respectively, edges to the 6-gon such that the 6-gon is partitioned into 3 or
4, respectively, empty 4-gons.

  9. _E9_

A $6$-gon with either a path on 3 vertices or a 4-cycle inside, connected as
depicted also in Fig. 1(a).

The proof of Lemma 3 is similar to the one of Lemma 2 and can be found in
Appendix 0.A. Note that Lemma 3 considers plane drawings. If $D$ has a
crossing, then $P(D)$ has a vertex of degree $4$. The only drawings in the
exceptions with a vertex with degree $4$ are shown in Fig. 1(a). It can be
shown that, when replacing the vertices of degree $4$ in any of them by a
crossing, the resulting drawings have $\operatorname{TAR}(D)\leq 60^{\circ}$.
A detailed proof of this fact can be found in Appendix 0.C and will be useful
for the proof of the next theorem.

((a))

((b))

Figure 1: (a) The drawings of exception E9. (b) A drawing $D$ of a graph with
$m\\!=\\!2n\\!-\\!6$ and $\operatorname{TAR}(D)>60^{\circ}$.

###### Theorem 2.1

Let $G$ be a graph with $n\geq 3$ vertices, $m$ edges and
$\operatorname{TAR}(G)>60^{\circ}$. Then $m\leq 2n-6$ except if $G$ is either
a graph of an exception for Lemma 3 or only consists of three vertices and one
edge (Exception E0 in Fig. 5).

###### Proof

Assume there exists a graph which is not in the list of exceptions for Lemma 3
with $\operatorname{TAR}(G)>60^{\circ}$. Consider a drawing $D$ of $G$ with
$\operatorname{TAR}(D)>60^{\circ}$ and its planarization $P(D)$.

Applying Lemma 1 to every component gives $m\leq 2m-6$, with the only
exception consisting of three vertices and one edge (Exception E0). Details
can be found in Appendix 0.D. So for the rest of the proof only consider
connected graphs.

If three edges cross in a single point, then in $P(D)$ this point has degree
$6$ and therefore an angle with at most $60^{\circ}$. Hence $P(D)$ has
$m_{P}=m+2\operatorname{cr}(D)$ edges and $n_{P}=n+\operatorname{cr}(D)$
vertices. Let $m=2n-c$. This is equivalent to $m_{P}=2n_{P}-c$. Since
$\operatorname{TAR}(P(D))\geq\operatorname{TAR}(D)>60^{\circ}$, by applying
Lemma 3 we get that $m_{P}\leq 2n_{P}-6$ or $P(D)$ is in the exceptions. If
$m_{P}\leq 2n_{P}-6$, then also $m\leq 2n-6$. If $P(D)$ is in the exceptions,
then, as observed before, $D$ is in the exceptions. ∎

The bound of Theorem 2.1 is the best possible in the sense that there are
infinitely many graphs with $m=2n-6$ and $\operatorname{TAR}(G)>60^{\circ}$.
Consider for example the layered $8$-gon with two edges in the middle depicted
in Fig. 1(b), which can be generalized to any $n=8k$ with $k\in\mathds{N}$. In
the full version of this work we present examples for every $n\geq 9$ and also
discuss plane drawings of planar graphs.

##  3 NP-hardness

Forman et al. [7] showed that the problem of determining whether there exists
a drawing of a graph with angular resolution of $90^{\circ}$ is -hard. Their
proof, which is by reduction from with exactly three different literals per
clause, also implies -hardness of deciding whether a graph has a drawing with
total angular resolution of $90^{\circ}$. We adapt their reduction to show
-hardness of the decision problem for $\operatorname{TAR}(G)\geq 60^{\circ}$.
A full version of the proof of Theorem 3.1 can be found in Appendix 0.E.

###### Theorem 3.1

It is -hard to decide whether a graph $G$ has $\operatorname{TAR}(G)\geq
60^{\circ}$.

######  Proof (sketch)

Given a formula with variables $x_{1},x_{2},\dots,x_{n}$ and clauses
$c_{1},c_{2},\dots,c_{m}$, where every clause contains exactly three different
literals, we first construct a graph $G$ for it. The basic building blocks of
$G$ consist of triangles, which must be equilateral in any drawing with total
angular resolution $60^{\circ}$.

We use three types of gadgets; see Fig. 2(a). The clause gadget has a
designated _clause vertex_ $C_{j}$ and the variable gadget has two _literal
vertices_ $X_{i,j},\overline{X}_{i,j}$ per clause $c_{j}$. For each gadget,
the embedding with total angular resolution $60^{\circ}$ is unique up to
rotation, scaling and reflection.

((a)) All used gadgets ((b)) Frame with clause gadgets

Figure 2: Gadgets and frame of the -hardness proof.

For connecting the gadgets, we build a 3-sided frame; see Fig. 2(b). It
consists of a straight _bottom path_ of $2n+2m-1$ triangles alternatingly
facing up and down, a sequence of $m$ clause gadgets stacked on top of each
other to the right (one for each clause, with the clause vertices
$C_{1},\ldots,C_{m}$ facing to the right), and a _top path_ of $2n+2m-1$
triangles alternatingly facing down and up. The leftmost $n$ vertices of
degree three on the upper side of the bottom path and the lower side of the
top path ($X_{1},\ldots,X_{n}$ and $X^{\prime}_{1},\ldots,X^{\prime}_{n}$) are
used for the variables: For each variable $x_{i}$, we add a variable gadget
and a connector gadget by identifying $A_{i,1}$ with $X_{i}$, $A_{i,2}$ with
$A_{i,3}$, and $A_{i,4}$ with $X^{\prime}_{i}$, respectively. Finally, a
clause-literal path consisting of three consecutive edges between $X_{i,j}$
($\overline{X}_{i,j}$) and $C_{j}$ is added whenever $x_{i}$
($\overline{x}_{i}$) is a literal of clause $c_{j}$.

The following holds for any drawing $D$ of the graph $G$ with $TAR(D)\geq
60^{\circ}$.  (_1_) The embedding of the frame is unique up to rotation,
scaling, and reflection. Hence we can assume that it is embedded as in Fig.
2(b).  (_2_) Each variable gadget together with its connector gadget must be
drawn vertically between its $X_{i}$ and $X^{\prime}_{i}$, either with all
$X_{i,j}$ to the right of the $\overline{X}_{i,j}$ or the other way around.
(_3_) All clause-literal paths leave from their clause vertices to the right,
and one path per clause leaves horizontally to the right.

We claim that $\operatorname{TAR}(G)\geq 60^{\circ}$ if and only if the
initial formula is satisfiable. For the one direction, consider a satisfying
truth assignment of the formula. We draw the variable gadgets with all true
literal sides to the right and scaled (via the connector gadgets) such that
different gadgets have their vertices at different heights, and we draw the
clause-literal paths as indicated in Fig. 3.

((a)) True connection, two versions

((b)) False connection

Figure 3: Connections between clause and literal vertices in the -hardness
proof.

For the other direction, consider a drawing of $C$ with
$\operatorname{TAR}(D)=60^{\circ}$. Using the straight lines $\ell_{1}$ and
$\ell_{2}$ sketched in Fig. 2(b), one can show that every clause-literal path
that leaves the clause vertex horizontally must end at a literal vertex facing
to the right. Setting the according literals to true gives a non-contradicting
variable assignment that in turn fulfills all clauses. ∎

##  4 Conclusion

In this work we have shown that, up to a finite number of well specified
exceptions of constant size, any graph $G$ with
$\operatorname{TAR}(G)>60^{\circ}$ has at most $2n-6$ edges. In addition we
have been able to obtain similar bounds for graphs with
${\operatorname{TAR}(G)\geq 90^{\circ}}$ and
$\operatorname{TAR}(G)>120^{\circ}$: For graphs with
$\operatorname{TAR}(G)\geq 90^{\circ}$ we have $m\leq 2n-2\sqrt{n}$ and for
$\operatorname{TAR}(G)>120^{\circ}$ we have $m\leq n$ for $n\geq 7$, which is
best possible. We conjecture that almost all graphs with
$\operatorname{TAR}(G)>\frac{k-2}{k}90^{\circ}$ have at most
$2n-2-\lfloor\frac{k}{2}\rfloor$ edges.

From a computational point of view, we have proven that finding a drawing of a
given graph with total angular resolution at least $60^{\circ}$ is -hard. The
same was known before for at least $90^{\circ}$ [7]. On the other hand, for
large angles, the recognition problem eventually becomes easy (for example,
$G$ can be drawn with $\operatorname{TAR}(G)>120^{\circ}$ if and only if it is
the union of cycles of at least 7 vertices and arbitrary paths). This yields
the following open problem: At which angle(s) does the decision problem change
from NP-hard to polynomially solvable?

## References

  * [1] Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. Journal of Combinatorial Theory, Series A 114, 563–571 (2007). https://doi.org/10.1016/j.jcta.2006.08.002
  * [2] Argyriou, E.N., Bekos, M.A., Symvonis, A.: The Straight-Line RAC Drawing Problem is NP-Hard. In: 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011). pp. 74–85. Springer, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-18381-2_6
  * [3] Argyriou, E.N., Bekos, M.A., Symvonis, A.: Maximizing the Total Resolution of Graphs. The Computer Journal 56(7), 887–900 (2013). https://doi.org/10.1093/comjnl/bxs088
  * [4] Bekos, M.A., Förster, H., Geckeler, C., Holländer, L., Kaufmann, M., Spallek, A.M., Splett, J.: A Heuristic Approach Towards Drawings of Graphs with High Crossing Resolution. In: Biedl, T., Kerren, A. (eds.) 26th International Symposium on Graph Drawing and Network Visualization (GD 2018). pp. 271–285. Springer, Cham (2018). https://doi.org/10.1007/978–3–030–04414–5_19
  * [5] Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theoretical Computer Science 412(39), 5156–5166 (2011). https://doi.org/10.1016/j.tcs.2011.05.025
  * [6] Dujmovic, V., Gudmundsson, J., Morin, P., Wolle, T.: Notes on large angle crossing graphs. Chicago Journal of Theoretical Computer Science 4, 1–14 (2011). https://doi.org/10.4086/cjtcs.2011.004
  * [7] Formann, M., Hagerup, T., Haralambides, J., Kaufmann, M., Leighton, F.T., Symvonis, A., Welzl, E., Woeginger, G.J.: Drawing Graphs in the Plane with High Resolution. SIAM Journal on Computing 22, 1035–1052 (1993). https://doi.org/10.1137/0222063
  * [8] Huang, W.: Using eye tracking to investigate graph layout effects. In: 2007 6th International Asia-Pacific Symposium on Visualization. pp. 97–100. IEEE (2007). https://doi.org/10.1109/APVIS.2007.329282
  * [9] Huang, W., Eades, P., Hong, S.H., Lin, C.: Improving multiple aesthetics produces better graph drawings. Journal of Visual Languages & Computing 24(4), 262–272 (2013). https://doi.org/10.1016/j.jvlc.2011.12.002
  * [10] Huang, W., Hong, S.H., Eades, P.: Effects of Crossing Angles. In: 2008 IEEE Pacific Visualization Symposium. pp. 41–46 (2008). https://doi.org/10.1109/PACIFICVIS.2008.4475457
  * [11] van Kreveld, M.: The quality ratio of RAC drawings and planar drawings of planar graphs. In: Brandes, U., Cornelsen, S. (eds.) 18th International Symposium on Graph Drawing (GD 2010). pp. 371–376. Springer, Berlin, Heidelberg (2010). https://doi.org/10.1007/978–3–642–18469-7_34

##  Appendix 0.A Proof of Lemma 3

###### Lemma 3

Let $D$ be a connected plane drawing on $n\geq 3$ vertices with
$\operatorname{TAR}(D)>60^{\circ}$. If $D$ is not combinatorially equivalent
to one of the exceptions E1–E9 as listed below and depicted in Fig. 5
(Appendix 0.B), then $m\leq 2n-6$.

  1. _E1_

A tree on at most 4 vertices.

  2. _E2_

An empty $4$-gon.

  3. _E3_

A $4$-gon with one additional vertex connected to one vertex of the $4$-gon.

  4. _E4_

An empty $5$-gon.

  5. _E5_

A $5$-gon with one inner vertex connected to two non-neighboring vertices of
the $5$-gon.

  6. _E6_

A $5$-gon with an edge inside, connected with 3 edges to the 5-gon such that
the 5-gon is partitioned into two empty 4-gons and one empty $5$-gon.

  7. _E7_

A $6$-gon with an additional diagonal between opposite vertices.

  8. _E8_

A $6$-gon with an additional vertex or edge inside, connected with 3 or 4,
respectively, edges to the 6-gon such that the 6-gon is partitioned into 3 or
4, respectively, empty 4-gons.

  9. _E9_

A $6$-gon with either a path on 3 vertices or a 4-cycle inside, connected as
depicted also in Fig. 1(a).

###### Proof

Let $D^{\prime}$ be a subdrawing of $D$ consisting of all vertices, which are
not on the unbounded cell and all edges, which are not incident to a vertex on
the unbounded cell. Assume $D^{\prime}$ has $n^{\prime}$ vertices and
$m^{\prime}$ edges. We consider different cases.

Case 1

The unbounded cell has size at least $7$. Then we have, by Lemma 1,

$m\leq
2n-2-\left\lceil\frac{k}{2}\right\rceil=2n-2-\left\lceil\frac{7}{2}\right\rceil\leq
2n-6.$

Case 2

The unbounded cell has size $4$. Then either our drawing has only one cell,
which is a case of Exception E1, or the outer boundary is a $4$-gon. In this
case we have $n=n^{\prime}+4$ and $m\leq m^{\prime}+5$. If there is at most
one vertex in the interior of the 4-gon, then we have Exception E2 or E3,
respectively. So we can assume that there are at least 2 vertices in the
interior. By Observation 1 we have at most one edge from a vertex on the
unbounded cell to the inside. Therefore, $D^{\prime}$ is connected and thus it
has at least one edge. So by Lemma 1 we have ${m^{\prime}\leq 2n^{\prime}-3}$.
With this we get

$\displaystyle m\leq m^{\prime}+5\leq 2n^{\prime}-3+5=2(n-4)+2=2n-6.$

Case 3

The unbounded cell has size $5$. If the unbounded cell has size $5$, the outer
boundary is a $5$-gon. The only other possibility would be a drawing $D$ of a
triangle with an attached edge, but in that case $\operatorname{TAR}(D)\leq
60^{\circ}$. If there are at most two adjacent vertices inside the 5-gon, then
we have one of Exceptions E4, E5, or E6. So we can assume that there are at
least 3 vertices in the interior. Moreover, $n=n^{\prime}+5$ holds. Due to
Observation 1, there are at most three edges connecting the interior to the
$5$-gon and the $5$-gon itself has $5$ edges, that is,
$m=m^{\prime}+5+3=m^{\prime}+8$. If $D^{\prime}$ is connected and has more
than 2 vertices, then the size of the unbounded cell is at least $3$ and we
have by Lemma 1 $m^{\prime}\leq 2n^{\prime}-4$. By applying Lemma 1 for every
connected component we also get $m^{\prime}\leq 2n^{\prime}-4$ if $D^{\prime}$
is disconnected. In these cases $m^{\prime}\leq 2n^{\prime}-4$ holds and we
have

$\displaystyle m$ $\displaystyle\leq m^{\prime}+8\leq 2n^{\prime}-4+8=2n-6.$

Case 4

The unbounded cell of our drawing $D$ has size $6$. So our drawing $D$ has
either only one (unbounded) cell (two cases of Exception E1), consists of two
triangles sharing a vertex ($\operatorname{TAR}(D)\leq 60^{\circ}$), or has as
boundary a $4$-gon with an attached edge or a $6$-gon. So there are two cases
we have to consider.

  * •

If the unbounded cell is a $4$-gon with an attached edge, we use the same
arguments as in Case 1. If the $4$-gon is empty, then we have again Exception
E3. If we have at least one point inside the 4-gon, then by Lemma 1 we have
$m^{\prime}\leq 2n^{\prime}-2$. So we get

$m=m^{\prime}+6\leq 2n^{\prime}-2+6=2(n^{\prime}+5)-6=2n-6.$

  * •

If the unbounded cell is a $6$-gon, then by Observation 1 we can have at most
$5$ edges connecting the interior to the 6-gon. First we assume that
$D^{\prime}$ is connected. If $\operatorname{TAR}(D)>60^{\circ}$, then
$\operatorname{TAR}(D^{\prime})>60^{\circ}$ and the drawing in $D^{\prime}$
fulfills ${m^{\prime}\leq 2n^{\prime}-5}$ by Lemma 2 or it is in the
exceptions of Lemma 2. Furthermore, we know $n=n^{\prime}+6$ and $m\leq
m^{\prime}+11$. If $m^{\prime}\leq 2n^{\prime}-5$, then

$\displaystyle m$ $\displaystyle\leq m^{\prime}+11\leq 2n^{\prime}-5+11=2n-6.$

So the only drawings where this does not hold are $6$-gons with a drawing
inside, which is in the exceptions in Lemma 2. This results in Exceptions E7
and E8, as $n^{\prime}<3$, and Exceptions E9, as they contain the two
exceptions of Lemma 2.

If $D^{\prime}$ is not connected and $\operatorname{TAR}(D)>60^{\circ}$, then
$m\leq 2n-6$ or $D^{\prime}$ consists of two non-adjacent vertices which are
connected to the $6$-gon with $5$ edges in total. This means that one of the
two inner vertices has degree at least $3$ in the drawing $D$. If one vertex
has degree 4, then there is a triangle in our drawing $D$ which means
$\operatorname{TAR}(D)\leq 60^{\circ}$. Otherwise, if one vertex has degree 3
and the other one has degree 2, then we have a drawing like in Fig. 4. The
grey shaded $4$-gon has 2 edges in the inside. So due to Observation 1 we have
$\operatorname{TAR}(D)\leq 60^{\circ}$. ∎

Figure 4: Two separated vertices inside a $6$-gon.

##  Appendix 0.B All exceptions

This appendix contains drawings depicting all exceptions of Lemma 3 and
Theorem 2.1 (Fig. 5).

Figure 5: All exceptions for Lemma 3 and Theorem 2.1

##  Appendix 0.C Replacing a vertex by a crossing in Exception E9

###### Lemma 4

If we replace the vertex of degree $4$ in a drawing of Fig. 1(a) with a
crossing, then the resulting drawings $D$ have $\operatorname{TAR}(D)\leq
60^{\circ}$.

###### Proof

Figure 6: Replacing vertex of degree $4$ of the drawing in Fig. 1(a) (left)
with a crossing.

If we replace the vertex of degree $4$ of the drawing in Fig. 1(a) (left) with
a crossing, then we get the drawing $D_{cr}$ in Fig. 6, where the dashed edge
is not part of the actual drawing. We want to show that
$\operatorname{TAR}(D_{cr})\leq 60^{\circ}$. As in Fig. 6 we denote $\angle
ACB$ as $\alpha$ and $\angle BCD$ as $\beta$ and both these angles are between
two edges of the drawing. Let $P_{1},P_{2}$ and $P_{3}$ be the other three
vertices on the unbounded cell. Since $C$ is a crossing, $C$ is inside the
pentagon $ABP_{1}P_{2}P_{3}$. The inner angles of a pentagon sum up to
$540^{\circ}$. All eight inner angles of the drawing, which are incident to
the convex hull have more than $60^{\circ}$. This implies $\angle BAC+\angle
ABC\leq 60^{\circ}$. Furthermore we have
$\alpha+\beta=180^{\circ}=\alpha+\angle BAC+\angle ABC$. This means we have
$\beta=\angle BAC+\angle ABC\leq 60^{\circ}$. But $\beta$ appears in $D_{cr}$
so we have $\operatorname{TAR}(D_{cr})\leq 60^{\circ}$. Let $D^{\prime}_{cr}$
be the drawing we get if we replace in the drawing in Fig. 1(a) (right) the
vertex of degree $4$ with a crossing. Then $D_{cr}$ is a subdrawing of
$D^{\prime}_{cr}$. So we get
$\operatorname{TAR}(D^{\prime}_{cr})\leq\operatorname{TAR}(D_{cr})\leq
60^{\circ}$. ∎

##  Appendix 0.D Disconnected drawings

###### Lemma 5

Let $D$ be an disconnected drawing on $n\geq 3$ vertices with
$\operatorname{TAR}(D)>60^{\circ}$. Then $m\leq 2n-6$ or $D$ consists of three
vertices and one edge (Exception E0 in Fig. 5).

###### Proof

Assume $D$ consists of components $C_{i}$, $1\leq i\leq l$, with $n_{i}\geq 1$
vertices and $m_{i}\geq 0$ edges. Furthermore,
$\operatorname{TAR}(C_{i})\geq\operatorname{TAR}(D)>60^{\circ}$ holds. By
Lemma 1 we get for every component $m_{i}\leq 2n_{i}-2$.

If $l\geq 3$, then we have

$m=\sum_{i=1}^{l}m_{i}\leq\sum_{i=1}^{l}(2n_{i}-2)=2n-2l\leq 2n-6.$

Otherwise $l=2$. If $C_{1}$ contains at least 2 edges, then the size of the
unbounded cell of $C_{1}$ is at least $3$. So we get $m_{1}\leq 2n_{1}-4$ by
Lemma 1. This gives

$m=m_{1}+m_{2}=2n_{1}-4+2n_{2}-2=2n-6.$

If $C_{1}$ and $C_{2}$ both consist of two vertices and an edge, then we have
$m=2\cdot 4-6=2$. If $D$ is a drawing on $3$ vertices and an edge, then we
have Exception E0. ∎

##  Appendix 0.E Proof of Theorem 3.1

###### Theorem 0.E.2

It is -hard to decide whether a graph $G$ has $\operatorname{TAR}(G)\geq
60^{\circ}$.

###### Proof

As input we are given a formula with variables $x_{1},x_{2},\dots,x_{n}$ and
clauses $c_{1},c_{2},\dots,c_{m}$, where every clause contains exactly three
different literals. We first construct a graph $G$ for the formula. The basic
building blocks of our construction consist of triangles, which, in order to
obtain a total angular resolution of $60^{\circ}$, must all be equilateral. We
use the following gadgets; see Fig. 2(a).

As clause gadget we use a sequence of four triangles that share a common
vertex and in which consecutive triangles share an edge. The middle vertex
with three incident edges, marked with $C_{j}$ in the figure, will be used to
connect the clause gadget to its literals. We denote $C_{j}$ as _clause
vertex_.

As variable gadget we use a triangle followed by a sequence of $m$ hexagons
and followed by another triangle. Each hexagon consists of six triangles
sharing the center point. Each non-extreme hexagon of the sequence is incident
to its neighboring hexagons via two “opposite” edges. The initial triangle is
incident to the first hexagon via the edge opposite to the incidence with the
second hexagon. The final triangle is incident to the last hexagon via the
edge opposite to the incidence with the second to last hexagon. The vertices
of the initial and the final triangle that are incident to none of the
hexagons are denoted as $A_{i,1}$ and $A_{i,2}$, respectively.

For each variable $x_{i}$, we assign one side of the hexagonal path to the
positive literal $x_{i}$ and the other to the negative literal
$\overline{x}_{i}$. The intermediate vertices of the $j$th hexagon of the path
are denoted with $X_{i,j}$ and $\overline{X}_{i,j}$, respectively, and called
_literal vertices_. They will be used for connecting a literal to its clause.

Additionally we use a connector gadget. It consists of two triangles with a
common edge. The two vertices that are incident to only one of the triangles
are denoted as $A_{i,3}$ and $A_{i,4}$, respectively.

Note that for all three gadgets, an embedding with total angular resolution
$60^{\circ}$ is unique up to rotation, scaling and reflection of the whole
gadget. Especially, for each gadget, all triangles are congruent.

For connecting the gadgets, we first build a rigid 3-sided frame as depicted
in Fig. 2(b). On the bottom, it consists of a straight path of $2n+2m-1$
triangles that alternatingly face up and down (the bottom path). On top of the
rightmost triangle of this path, we add a sequence of $m$ clause gadgets
stacked on top of each other (one for each clause, with the clause vertices
$C_{1},\ldots,C_{m}$ facing to the right). The top consists of a straight path
of $2n+2m-1$ triangles that alternatingly face down and up (the top path). We
denote the leftmost $n+1$ vertices of degree three on the upper side of the
bottom path with $X_{1},\ldots,X_{n}$, and $B_{1}$. The leftmost $n+1$
vertices of degree three on the lower side of the top path are denoted
$X^{\prime}_{1},\ldots,X^{\prime}_{n}$, and $B_{2}$. As an embedding with
total angular resolution $60^{\circ}$ of this frame again is again unique up
to rotation, scaling, and reflection, we assume without loss of generality
that it is embedded as depicted in Fig. 2(b). Then, for every $1\leq i\leq n$,
$X^{\prime}_{i}$ and $X_{i}$ lie on a vertical line. Further, the line
$\ell_{1}$ spanned by $B_{1}$ and $C_{m}$ has slope $60^{\circ}$ and the line
$\ell_{2}$ through $B_{2}$ and $C_{1}$ has slope $-60^{\circ}$.

We next add the variable gadgets in the following way. For each variable
$x_{i}$, we identify the vertex $A_{i,1}$ of its gadget with $X_{i}$. Further,
we connect the gadget to $X^{\prime}_{i}$ via a connector gadget by
identifying $A_{i,2}$ with $A_{i,3}$ and $A_{i,4}$ with $X^{\prime}_{i}$,
respectively. In any drawing with total angular resolution $60^{\circ}$ of the
construction so far, each variable gadget together with its connector gadget
must be drawn vertically between $X_{i}$ and $X^{\prime}_{i}$. Further, the
gadgets can be scaled by adapting the height of the connector gadget.
Independent of the scaling factor, the left side of each variable gadget is
always to the left of the lines $\ell_{1}$ and $\ell_{2}$. Directionwise,
variable gadgets can be drawn in two ways: either all $X_{i,j}$ are to the
right of the $\overline{X}_{i,j}$ or the other way around.

To complete the construction, we add a path consisting of three consecutive
edges between $X_{i,j}$ ($\overline{X}_{i,j}$) and $C_{j}$ whenever $x_{i}$
($\overline{x}_{i}$) is a literal of clause $c_{j}$. To obtain a total angular
resolution of $60^{\circ}$ at every clause vertex $C_{i}$, all of these paths
must start from $C_{i}$ towards the right and one must start horizontally. We
claim that the constructed graph $G$ has a drawing $D$ with
$\operatorname{TAR}(D)\geq 60^{\circ}$ if and only if the initial formula is
satisfiable.

Assume first that the formula is satisfiable. Consider a truth assignment of
the variables that satisfies the formula. We draw each variable gadget such
that the side corresponding to its true literal is on the right. Further, we
scale all the variable gadgets such that no two vertices of different variable
gadgets or of a variable gadget and a clause gadget lie on a horizontal line
(except for the vertices $X_{i}$). For every clause $c_{j}$, we choose a
literal $v_{i}\in\\{x_{i},\overline{x}_{i}\\}$ of $c_{i}$ which is true. We
draw the path between the corresponding clause vertex $C_{j}$ and the literal
vertex $V_{i,j}$ by starting with a horizontal edge from $C_{j}$ to the right,
continuing with a $\pm 60^{\circ}$ edge to the right and up to the height of
$V_{i,j}$, and ending with a horizontal edge to $V_{i,j}$. For the other
literals of $c_{j}$ we draw a $\pm 60^{\circ}$ edge from $C_{j}$ to the right,
followed by a horizontal edge to the left and a $\pm 60^{\circ}$ edge to the
left or right, depending on whether $v_{i}$ is true or false; see Fig. 3. As
all edges of the resulting drawing $D$ are either horizontal or under an angle
of $\pm 60^{\circ}$, we have $\operatorname{TAR}(D)=60^{\circ}$ as desired.

For the other direction, assume that $G$ admits a drawing $D$ with
$\operatorname{TAR}(D)=60^{\circ}$. In $D$, consider a clause vertex $C_{j}$
and the path $P=C_{j}M_{1}M_{2}V_{i,j}$ which starts horizontally at $C_{j}$.
Then the literal vertex $V_{i,j}$ must be on the right side of its variable
gadget: If $V_{i,j}$ is a left vertex of a variable gadget, then $P$ must
enter $V_{i,j}$ from the left under an angle of at most $\pm 60^{\circ}$ with
respect to the horizontal line. Hence $M_{2}$ lies to the left of the lines
$\ell_{1}$ and $\ell_{2}$. On the other hand, the second vertex $M_{1}$ of $P$
lies horizontally to the right of $C_{j}$. However, to respect the
$60^{\circ}$ restriction at $M_{1}$, $M_{2}$ must lie to the right of the
lines $\ell_{1}$ and $\ell_{2}$, a contradiction. Now consider the set of
literal vertices that are an endpoint of a path starting horizontally at some
clause vertex. As these literal vertices are on the right side of their
corresponding variable gadgets, the set does not contain any pair
$X_{i,j},\overline{X}_{i,k}$. By setting all the corresponding literals to
true, we obtain a non-contradicting partial truth assignment of the variables
that satisfies the formula since for every clause $c_{j}$ the literal $v_{i}$
corresponding to $V_{i,j}$ is true. ∎