Aligned Drawings of Planar Graphs?
Tamara Mchedlidze1 , Marcel Radermacher1 , and Ignaz Rutter2

arXiv:1708.08778v3 [] 21 Nov 2017

1

Department of Computer Science, Karlsruhe Institute of Technology, Germany
2
Department of Mathematics and Computer Science, TU Eindhoven, The
Netherlands,
mched@iti.uka.de, radermacher@kit.edu, i.rutter@tue.nl

Abstract. Let G be a graph topological embedded in the plane and
let A be an arrangement of pseudolines intersecting the drawing of G.
An aligned drawing of G and A is a planar polyline drawing Γ of G
with an arrangement A of lines so that Γ and A are homeomorphic
to G and A. We show that if A is stretchable and every edge e either
entirely lies on a pseudoline or intersects at most one pseudoline, then
G and A have a straight-line aligned drawing. In order to prove these
results, we strengthen the result of Da Lozzo et al. [5], and prove that a
planar graph G and a single pseudoline L have an aligned drawing with
a prescribed convex drawing of the outer face. We also study the more
general version of the problem where only a set of vertices is given and
we need to determine whether they can be collinear. We show that the
problem is N P-complete but fixed-parameter tractable.

1

Introduction

Two fundamental primitives for highlighting structural properties of a graph in
a drawing are alignment of vertices such that they are collinear, and geometric
separation of unrelated graph parts, e.g., by a straight line. Both these techniques
have been previously considered from a theoretical point of view in the case of
planar straight-line drawings.
Da Lozzo et al. [5] study the problem of producing a planar straight-line
drawing of a given embedded graph G = (V, E), i.e., G has a fixed combinatorial
embedding and a fixed outer face, such that a given set S ⊆ V of vertices is
collinear. It is clear that if such a drawing exists, then the line containing the
vertices in S is a simple curve starting and ending at infinity that for each edge
e of G either fully contains e or intersects e in at most one point, which may
be an endpoint. We call such a curve a pseudoline with respect to G. Da Lozzo
et al. [5] show that this is a full characterization of the alignment problem, i.e.,
a straight-line drawing where the vertices in S are collinear exists if and only
if there exists a pseudoline L with respect to G that contains the vertices in S.
?

Work was partially supported by grant WA 654/21-1 of the German Research Foundation (DFG). Preliminary work appeared in F. Frati and K. Ma, editors, Proceedings
of the 25th International Symposium on Graph Drawing (GD ’17).

(a)

(b)

(c)

Fig. 1: (Pseudo-) Lines are denoted by blue curves, edges are black. Aligned
Drawing (b) of a 2-aligned planar graph (a). (c) A non-stretchable arrangement
of 9 pseudolines (blue and black), which can be seen as a stretchable arrangement
of 8 pseudolines (blue) and an edge (black solid).

However testing whether such a pseudoline exists is an open problem, which we
consider in this paper.
Likewise, for the problem of separation, Biedl et al. [1] considered so-called
HH-drawings where, given an embedded graph G = (V, E) and a partition
˙
V = A∪B,
one seeks a planar drawing of G in which A and B can be separated
by a line. Again, it turns out that such a drawing exists if and only if there
exists a pseudoline L with respect to G such that the vertices in A and B are
separated by L. As a side-result Cano et al. [2] extend the result of Biedl et al.
to planar straight-line drawings with a given star-shaped outer face.
The aforementioned results of Da Lozzo et al. [5] show that given a pseudoline
L with respect to G one can always find a planar straight-line drawing of G such
that the vertices on L are collinear and the vertices contained in the halfplanes
defined by L are separated by a line L. In other words, a topological configuration
consisting of a planar graph G and a pseudoline with respect to G can always
be stretched. In this paper we initiate the study of this stretchability problem
with more than one given pseudoline.
More formally, a pair (G, A) is a k-aligned graph if G = (V, E) is a planar
embedded graph and A = {L1 , . . . , Lk } is an arrangement of (pairwise intersecting) pseudolines with respect to G. If the number k of curves is clear from the
context, we drop it from the notation and simply speak of aligned graphs. For
1-aligned graphs we write (G, L) instead of (G, {L}). Let A = {L1 , . . . , Lk } be
a line arrangement and Γ be planar drawing of G. A tuple (Γ, A) is an aligned
drawing of (G, A) if and only if the following properties hold; refer to Fig. 1(a-b).
(i) The arrangement of A is homeomorphic to the arrangement of A (i.e., A is
stretchable), (ii) Γ is homeomorphic to the planar embedding of G, (iii) each line
Li intersects in Γ the same vertices and edges as Li in G, and it does so in the
same order. We focus on straight-line aligned drawings. For brevity, unless stated
otherwise, the term aligned drawing refers to a straight-line drawing throughout
this paper.
Note that the stretchability of A is a necessary condition for the existence
of an aligned drawing. Since testing stretchability is N P-complete [14,15], we
2

assume that a geometric realization A of A is provided. Line arrangements of size
up to 8 are always stretchable [11], and only starting from 9 lines non-stretchable
arrangements exist; see the Pappus configuration [12] in Fig. 1c. This figure also
illustrates an example of an 8-aligned graph with a single edge that does not
have an aligned drawing. It is conceivable that in practical applications, e.g.,
stemming from user interactions, the number of lines to stretch is small, justifing
the stretchability assumption.
The aligned drawing convention generalizes the problems studied by Da Lozzo
et al. and Biedl et al. who concentrated on the case of a single line. We study a
natural extension of their setting and ask for alignment on general line arrangements.
In addition to the strongly related work mentioned above, there are several other works that are related to the alignment of vertices in drawings. Dujmović [6] shows that every n-vertex
√ planar graph G = (V, E) has a planar
straight-line drawing such that Ω( n) vertices are aligned, and Da Lozzo et
al. [5] show that in planar treewidth-3 and planar treewidth-k graphs, one can
align Θ(n) and Ω(k 2 ) vertices, respectively. Chaplik et al. [3] study the problem
of drawing planar graphs such that all edges can be covered by k lines. They
show that it is N P-hard to decide whether such a drawing exists. The complexity of deciding whether there exists a drawing where all vertices lie on k lines is
an open problem [4]. Drawings of graphs on n lines where a mapping between
the vertices and the lines is provided have been studied by Dujmović et al. [7,8].
Contribution & Outline. After introducing notation in Section 2, we first study
the topological setting where we are given a planar graph G and a set S of
vertices to align in Section 3. We show that the problem is N P-complete but
fixed-parameter tractable (FPT) with respect to |S|. Afterwards, in Section 4,
we consider the geometric setting where we seek an aligned drawing of an aligned
graph. Based on our proof strategy in Section 4.1, we strengthen the result of
Da Lozzo et al. and Biedl et al. in Section 4.2, and show that there exists a 1aligned drawing of G with a given convex drawing of the outer face. In Section 4.3
we consider k-aligned graphs with a stretchable pseudoline arrangement, where
every edge e either entirely lies on a pseudoline or intersects with at most one
pseudoline, which can either be in the interior or an endpoint of e. We utilize
the result of Section 4.2 to prove that every such k-aligned graph has an aligned
drawing, for any value of k.

2

Preliminaries

Let A be a pseudoline arrangement of a set of k pseudolines L1 , . . . , Lk and
(G, A) be an aligned graph with n vertices. The set of cells in A is denoted by
cells(A). A cell is empty if it does not contain a vertex of G. Removing from a
pseudoline its intersections with other pseudolines gives its pseudosegments.
Let G = (V, E) be a planar embedded graph with vertex set V and edge
set E. We call v ∈ V interior if v does not lie on the boundary of the outer
face of G. An edge e ∈ E is interior if e does not lie entirely on the boundary
3

(a) (1, 0, ⊥)

(b) (1, 0, 0)

(c) (2, 1, 0)

Fig. 2: Examples for the alignment complexity of an aligned graph.

of the outer face of G. An interior edge is a chord if it connects two vertices on
the outer face. A point p of an edge e is an interior point of e if p is not an
endpoint of e. A triangulation is a biconnected planar embedded graph whose
inner faces are all triangles and whose outer face is bounded by a simple cycle.
A triangulation of a graph G is a triangulation that contains G as a subgraph.
A k-aligned triangulation of (G, A) is a k-aligned graph (GT , A) with GT being
a triangulation of G. A Graph G0 is a subdivision of G if G0 is obtained by
placing subdivision vertices on edges of G. For a graph G and an edge e of G
the graph G/e is obtained from G by contracting e and merging the resulting
multiple edges and removing self-loops. A k-wheel is a simple cycle with k vertices
on the outer face and one interior vertex. Let Γ be a drawing of G and let C be
a cycle in G. We denote with Γ [C] the drawing of C in Γ .
A vertex is Li -aligned (or simply aligned to Li ) if it lies on the pseudoline Li .
A vertex that is not aligned is free. An edge e is Li -aligned (or simply aligned ) if it
completely lies on Li . Let Ealigned be the set of all aligned edges. An intersection
vertex lies on the intersection of two pseudolines Li and Lj . A non-aligned edge
is i-anchored (i = 0, 1, 2) if i of its endpoints are aligned to distinct curves.
An L-aligned edge is i-anchored (i = 0, 1, 2) if i of its endpoints are aligned to
distinct curves which are different from L. For example, the single aligned edge
in Fig. 2a is 1-anchored. Let Ei be the set of i-anchored edges; note that, the set
of edges is the disjoint union E0 ∪· E1 ∪· E2 . A 0-anchored, 0-crossed, non-aligned
edge is also called free. An edge e is (at most) l-crossed if (at most) l distinct
pseudolines intersect e in its interior. A non-empty edge set A ⊂ E is l-crossed
if l is the smallest number such that every edge in A is at most l-crossed.
The alignment complexity of an aligned graph G in a way describes how “complex” the relationship between the graph G and the line arrangement L1 , . . . , Lk
is and formally is defined as a triple (l0 , l1 , l2 ) , where li , i = 0, 1, 2, describes the
“complexity of i-anchored edges”, i.e., it indicates that Ei is at most li -crossed
or has to be empty, if li = ⊥. For example, an aligned graph where every vertex
is aligned and every edge has at most l interior intersections has the alignment
complexity (⊥, ⊥, l). For further examples, see Fig. 2.
4

3

Complexity and Fixed-Parameter Tractability

In this section we deal with the topological setting where we are given a planar
embedded graph G = (V, E) and a subset S ⊆ V to be collinear. According to
Da Lozzo et al. [5], this is equivalent to the existence of a pseudoline L with
respect to G passing exactly through the vertices in S. We refer to this problem
as pseudoline existence problem and the corresponding search problem is referred
to as pseudoline construction problem. Using techniques similar to Fößmeier and
Kaufmann [9], we can show that the pseudoline existence problem is N P-hard.
Let G? + V be the graph obtained from the dual graph G? = (V ? , E ? ) of
G = (V, E) by placing every vertex v ∈ V in its dual face v ? and connecting it
to every vertex on the boundary of the face v ? .
Lemma 1. Let G = (V, E) be a 3-connected 3-regular planar graph. There exists
a pseudoline through V with respect to the graph G? + V if and only if G is
Hamiltonian.
Proof. Recall that the dual of a 3-connected 3-regular graph is a triangulation.
Assume that there exists a pseudoline L through V with respect to G? + V .
Then the order of appearance of the vertices of G? + V on L defines a sequence
of adjacent faces in G? , i.e., vertices of the primal graph G that are connected
via primal edges. This yields a Hamiltonian cycle in G.
Let C be a Hamiltonian cycle of G and consider a simultaneous embedding
of G and G? + V on the plane, where each pair of a primal and its dual edge
intersects exactly once. Thus, the cycle C crosses each dual edge e at most once
and passes through exactly the vertices V . There is a vertex v on the cycle C
such that v lies in the unbounded face of G? + V . Thus, the cycle C can be
interpreted as a pseudoline L(V ) in G? + V through all vertices in V by splitting
it in the unbounded face of G? + V .

Since computing a Hamiltonian cycle in 3-connected 3-regular planar graphs
is N P-complete [10], we get that the pseudoline construction problem is N Phard. On the other hand, we can guess a sequence of vertices, edges and faces of
G, and then test in polynomial time whether this corresponds to a pseudoline L
with respect to G that traverses exactly the vertices in S. Thus, the pseudoline
construction problem is in N P. This proves the following theorem.
Theorem 1. The pseudoline existence problem is N P-complete.
In the following, we show that the pseudoline construction problem is fixedparameter tractable with respect to |S|. To this end, we construct a graph Gtr =
(V tr , E tr ) and a set S tr ⊆ V tr with |S tr | ≤ |S|+1 such that Gtr contains a simple
cycle traversing all vertices in S tr if and only if there exists a curve L that passes
exactly through the vertices of S such that (G, L) is an aligned graph.
We observe that if the vertices S of a positive instance are not independent,
they can only induce a linear forest, i.e., a set of paths, as otherwise there is
no pseudoline through the vertices S with respect to G. We call the edges on
5

e
ve

vfin

vfout
v

Fig. 3: The black and red edges depict a single face of the input graph G. Red
and blue edges build the transformed graph Gtr . Red squared vertices illustrate
the set S tr . Blue dashed edges sketch the clique edges between clique vertices
(filled blue).

these paths aligned edges. An edge that is not incident to a vertex in S is called
crossable, in the sense that only crossable edges can be crossed by L, otherwise
L is not pseudoline with respect to G. Let Sep ⊆ S be the subset of vertices
that are endpoints of the paths induced by S (an isolated vertex is a path of
length 0). We construct Gtr in several steps; refer to Fig. 3.
Step 1: Let G0 be the graph obtained from G by subdividing each aligned edge
e with a new vertex ve and let S tr be the set consisting of all isolated vertices
in S and the new subdivision vertices. Additionally, we add to G0 one new
vertex o that we embed in the outer face of G and also add to S tr . Observe
that by construction |S tr | ≤ |S| + 1. Finally, subdivide each crossable edge e
by a new vertex ve . We call these vertices traversal nodes and denote their
set by T = Sep ∪{ve | e is crossable}∪{o}. Intuitively, a curve will correspond
to a path that uses the vertices in Sep to hop onto paths of aligned edges
and the subdivision vertices of crossable edges to traverse from one face to
another. Moreover, the vertex o ∈ S tr plays a similar role, forcing the curve
to visit the outer face.
Step 2 For each face f of G we perform the following construction. Let T (f )
denote the traversal nodes that are incident to f . For each vertex v ∈ T (f )
we create two new vertices vfin and vfout , add the edges vvfin and vvfout to G0 ,
and embed them in the interior of f . Finally, we create a clique C(f ) on the
vertex set {vfin , vfout | v ∈ T (f )}, and embed its edges in the interior of f .
Step 3 To obtain Gtr remove all edges of G0 that correspond to edges of G
except those that stem from subdividing an aligned edge of G.
Lemma 2. There exists a curve L traversing exactly the vertices in S such that
(G, L) is an aligned graph if and only if there exists a simple cycle in Gtr that
traverses all vertices in S tr .
6

vfin

vfout

vfout
00
vfin00

ve

v
vfout
0

vfin0

(a)

(b)

Fig. 4: (a) A pseudoline (thick green) traversing a path of aligned edges (thin
red). (b) A path (thick green) in Gtr visiting consecutive vertices in S tr (red
squared).

Proof. Suppose C is a cycle in Gtr that visits all vertices in S tr . Without loss
of generality, we assume that there is no face f such that C contains a subpath
from vfin via v to vfout (or its reverse) for some vertex v ∈ T (f ) \ Sep . If this is
the case, we simply shortcut this path by the edge vfin vfout ∈ C(f ).
Consider a path P of aligned edges in G that contains at least one edge; refer
to Fig. 4. By definition, C visits all the subdivision vertices ve ∈ S tr of the edges
of P , and thus it enters P on an endpoint of P , traverses P and leaves P at the
other endpoint. All isolated vertices of S are contained in S tr , and therefore C
indeed traverses all vertices in S (and thus also all aligned edges). As described
above, Gtr is indeed a topological graph, and thus C corresponds to a closed
curve ρ that traverses exactly the vertices in S and the aligned edges. We now
show that ρ can be transformed to a pseudoline with respect to G.
Let e be a non-aligned edge of G that has a common point with ρ in its
interior; see Fig. 5. Thus, C contains the subdivision vertex ve . In particular,
this implies that e is crossable. Moreover, from our assumption on C, it follows
0
that C enters ve via vfin or vfout and leaves it via vfin0 or vfout
0 , where f and f are the
0
faces incident to e, and it is f 6= f as we could shortcut C otherwise. Therefore,

f0

e

vfin0
f

vfout
0

(a)

vfout

ve
vfin
(b)

Fig. 5: (a) A pseudoline (thick green) passing through a non-aligned edge. (b)
A path (thick green) in Gtr traversing a subdivision vertex ve (blue non-filled
square). Black (dashed) segments are edges of G.
7

β
α

γ
δ

Fig. 6: Resolving an intersection by exchanged the intersecting segments (red)
with non-intersecting segments (green).

ρ indeed intersects e and uses it to traverse to a different face of G. Moreover,
since e has only a single subdivision vertex in Gtr and C is simple, it follows
that e is intersected only once. Thus ρ is curve that intersects all vertices in S,
traverses all aligned edges, and crosses each edge of G (including the endpoints)
at most once. Moreover, ρ traverses the outer face since C contains o.
The only reasons why ρ is not necessarily a pseudoline with respect to G are
that it is a closed curve and it may cross itself . However, we can break ρ in
the outer face and route both ends to infinity, and remove such self-intersections
locally as follows; see Fig. 6. Consider a circle D around an intersection I that
neither contains a second self-intersection nor a vertex, nor an edge of G. Let
α, β, γ, δ be the intersections of D with L. We replace the pseudosegment αγ
with a pseudosegment αβ, and βδ with a pseudosegment γδ. We route the pseudosegments αβ and γδ through the interior of D such that they do not intersect.
respect to G that contains exactly the vertices in S such that (G, L) is an aligned
graph.
For the converse assume that L is a pseudoline that traverses exactly the
vertices in S such that (G, L) is an aligned graph. The pseudoline L can be split
into three parts L1 , L2 and L3 such that L1 and L3 have infinite length and
do not intersect with G, and L2 has its endpoints in the outer face of G. We
transform L into a closed curve L0 by removing L1 , L3 and adding a new piece
connecting the endpoints of L2 without intersecting L2 or G. Additionally, we
choose an arbitrary direction for L0 in order to determine an order of the crossed
edges and vertices.
We show that Gtr contains a simple cycle traversing the vertices in S tr . By
definition L0 consists of two different types of pieces, see Fig. 4. The first type
traverses a path of aligned edges between two vertices in Sep . The other type
traverses a face of G by entering and exiting it either via an edge or from a
vertex in Sep ; see Fig. 7. We show how to map these pieces to paths in Gtr ; the
cycle C is obtained by concatenating all these paths.
Pieces of the first type indeed correspond directly to a path in Gtr ; see Fig. 4.
Consider now a piece π of the second type traversing a face f ; refer to Fig. 7.
The piece π enters f either from a vertex in Sep or by crossing a crossable edge e.
In either case, T (f ) contains a corresponding traversal node u. Likewise, T (f )
contains a traversal node v for the edge or vertex that L0 intersects next. We
8

out
tr
map π to the path uuin
f vf v in G . By construction, paths corresponding to
0
consecutive pieces of L share a traversal node, and therefore concatenating all
paths yields a cycle C in G? . Moreover, C is simple, since L0 intersects each
edge and each vertex at most once. Note that C contains at least one edge of
the outer face f0 (as L0 traverses the outer face), and we modify C so that it
also traverses the special vertex o.
It remains to show that C contains all vertices in S tr . There are three types of
vertices in S tr ; the subdivision vertices of aligned edges, the isolated vertices in
S, and the special vertex o. The latter is in C by the last step of the construction.
The isolated vertices in S are traversed by L0 and contained in Sep , and they
are therefore visited also by C. Finally, the subdivision vertices of aligned edges
are traversed by the paths corresponding to the first type of pieces, since L0
traverses all aligned edges.


Theorem 2 (Wahlström [16]). Given a graph G = (V, E) and a subset S ⊆
V , it can be tested in O(2|S| poly(|V |)) time whether a simple cycle through the
vertices in S exists. If affirmative the cycle can be reported within the same
asymptotic time.
Theorem 3. The pseudoline construction problem can be solved in O(2|S| poly(|V |))
time.
Proof. Let G = (V, E) with S ⊆ V be an instance of the pseudoline construction
problem with n = |V |. By Lemma 2 the pseudoline construction problem is
equivalent to determining whether Gtr contains a simple cycle visiting all vertices
in S tr . Since the size of Gtr is O(n2 ) and it can be constructed in O(n2 ) time,
and |S tr | ≤ |S| + 1, Theorem 2 can be used to solve the latter problem in the
desired running time.

We note that indeed the construction of Gtr only allows to leave a path of
aligned edges at an endpoint in Sep . Therefore, a single vertex in S tr for each
path of aligned edges would be sufficient to ensure that C traverses the whole
path. Thus, by removing all but one vertex for each such path from S tr we obtain
an algorithm that is FPT with respect to the number of paths induced by S.

u

uout
f

uin
f

vfin
vfout

(a)

v

(b)

Fig. 7: (a) A pseudoline piece π (thick green) passing through a face f . (b) Path
(thick green) in Gtr corresponding to π.
9

Corollary 1. The pseudoline construction problem can be solved in O(2P poly(|V |))
time, where P is the number of paths induced by the vertex set S to be aligned.

4

Drawing Aligned Graphs

We show that every aligned graph where each edge either entirely lies on a
pseudoline or is intersected by at most one pseudoline, i.e., alignment complexity
(1, 0, ⊥), has an aligned drawing. For 1-aligned graphs we show the stronger
statement that every 1-aligned graph has an aligned drawing with a given aligned
convex drawing of the outer face. We first present our proof strategy and then
deal with 1- and k-aligned graphs.
4.1

Proof Strategy

Our general strategy for proving the existence of aligned drawings of an aligned
graph (G, A) is as follows. First, we show that we can triangulate (G, A) by
adding vertices and edges without invalidating its properties. We can thus assume
that our aligned graph (G, A) is an aligned triangulation. Second we show that,
unless G is a specific graph (e.g., a k-wheel or a triangle), it contains an aligned
or a free edge. Third, we exploit the existence of such an edge to reduce the
instance. Depending on whether the edge is contained in a separating triangle
or not, we either decompose along that triangle or contract the edge. In both
cases the problem reduces to smaller instances that are almost independent. In
order to combine solutions, it is, however, crucial to use the same arrangement
of lines A for both of them.
In the following we introduce the necessary tools used for all three steps on
k-aligned graphs of alignment complexity (1, 0, ⊥). Recall, that for this class
(i) every non-aligned edge is 1-crossed, (ii) every 1-anchored edge has no intersections, and (iii) there is no edge with its endpoints on two pseudolines.
Lemmas 3 – 6 shows that every aligned graph has an aligned triangulation with the same alignment complexity. If G contains a separating triangle,
Lemma 7 shows that (G, A) admits an aligned drawing if both split components have an aligned drawing. Finally, with Lemma 8 we obtain a drawing of
(G, A) from a drawing of the aligned graph (G/e, A) where one special edge e is
contracted.
Lemma 3. Let (G, A) be a k-aligned graph with two distinct vertices u, v incident to a common face f . Then there is a k-aligned graph (G0 , A) obtained from
G by adding a path P from u to v in the interior of f . The edge set E(P ) has
alignment complexity (1, 0, ⊥) and does not contain aligned edges. The size of P
is in O(k 2 n).
Proof. We obtain a k-aligned graph (G0 , A) by routing a path P from u to v
through the interior of f ; compare Fig. 8. We construct P such that it has a
vertex in every cell of A it traverses. As each of the O(k 2 ) cells in A may be
subdivided into O(n) smaller cells by f , a shortest path from u to v contains
O(k 2 n) vertices.

10

u

v

Fig. 8: Connecting two vertices in black pseudoline arrangement A and the interior of a green face f .

qi

qi
u

y

v
w
(a)

w
v

y

x

v

x u

v

y

(b)

(c)

x

(d)

Fig. 9: Black lines indicate a face f of G. Light green edges or vertices are newly
added into f . Blue lines denote the pseudoline arrangement. (a) Isolation of
an intersection. (b-c) Isolation of an aligned edge or vertex. (d) Isolation of a
pseudosegment.

Lemma 4. Let (G, A) be a k-aligned graph. Then there exists a biconnected kaligned graph (G0 , A) that contains G as a subgraph. The set E(G0 ) \ E(G) has
alignment complexity (1, 0, ⊥) and does not contain aligned edges. The size of
E(G0 ) \ E(G) is in O(k 2 n2 ).
Proof. While G is not connected, we use Lemma 3 to connect two vertices of
distinct connected components that lie on the boundary of a common face. Afterwards, we use Lemma 3 to iteratively connect vertices from different biconnected
components. This results in the claimed biconnected k-aligned graph (G0 , A).
Since there are O(n) connected components and O(n) cut vertices, it follows
that Lemma 3 is applied O(n) times, and hence G0 has size O(k 2 n2 ).

Lemma 5. Let (G, A) be a biconnected k-aligned graph of alignment complexity
(1, 0, ⊥). There exists a k-aligned triangulation (GT = (VT , ET ), A) of (G, A)
whose size is O(k 4 n). The set E(GT ) \ E(G) has alignment complexity (1, 0, ⊥)
and does not contain aligned edges.
Proof. We call a face non-triangular, if its boundary contains more than three
vertices. An aligned vertex v or an aligned edge e is isolated if all faces with v
11

or e on its boundary are triangles. A pseudosegment s is isolated if s does not
intersect the interior of a non-triangular face. Our proof distinguishes four cases.
Each case is applied exhaustively in this order. Let f be a non-triangular face.
1. If the interior of f contains the intersection of two or more pseudolines, we
split the face, so that there is a vertex that lies on the intersection.
2. If the boundary of a face has an aligned vertex or an aligned edge, we isolate
the vertex or the edge from f .
3. If the interior of a face f is intersected by a pseudoline L, then it subdivides
L into a set of pseudosegments. We isolate each of the psedudosegments
independently.
4. Finally, if none of the previous cases apply, i.e., neither the boundary nor
the interior of f contain parts of a pseudoline, the face f can be triangulated
with a set of additional free edges.
Let Af be the arrangement of A and f restricted to the interior of f .
1. Let f be a non-triangular face whose interior contains an intersection of
a set of pseudolines; see Fig. 9a. We place a vertex x on the intersection.
We obtain a biconnected aligned graph with the application of Lemma 4.
There are at most O(k 2 ) intersections. Isolating each uses at most O(k 2 n)
additional vertices and edges. Thus, in total the isolation of all intersections
increases the graph size by O(k 4 n).
2. Let f be a non-triangular face with an aligned vertex or an aligned edge uv
on its boundary. Further, the interior of f does not contain the intersection
of a set of pseudolines; see Fig. 9b and 9c. In case of an aligned vertex we
simply assume u = v. Since G is biconnected, there exist two edges xu, vy on
the boundary of f . There are at most 2k cells C 1 , . . . , C l ∈ cells(Af ), l ≤ 2k
with u or v on their boundary, such that C i is adjacent to C i+1 , i < l. We
construct an aligned graph (G0 , A) from (G, A) as follows. We place a vertex
qi in the interior of each cell C i , i ≤ l. Let q0 = x and ql+1 = y. We insert
edges ei = qi qi+1 , i = 0, . . . , l in the interior of f and so that the interior of
ei crosses the common boundary of C i and C i+1 exactly once and it crosses
no other boundary. Thus, each edge ei is either at most 1-anchored and 0crossed, if it is incident to x or y, or otherwise 0-anchored and 1-crossed. The
added path splits f into two face f 0 , f 00 with a unique face f 0 containing u
and v on its boundary. If w ∈ {u, v} is on the boundary of cell C i , we insert
an edge wqi . Each edge wqi is 1-anchored and 0-crossed. Let C i and C i+1
be two cells incident to w. Then, the vertices w, qi , qi+1 form a triangle. If
u 6= v, there is a unique cell C i incident to u and v. Hence, the vertices u, v, qi
form a triangle. Moreover, for 1 ≤ i ≤ l, every edge uqi and vqi is incident to
two triangles. Therefore, f 0 is triangulated. The number of aligned edges and
aligned vertices of f 00 is one less compared to f . Hence, we can inductively
proceed on f 00 .
Assume the aligned vertex v is a vertex on an intersection of a set of pseudolines. Then, v is incident to O(k) cells and lies on the boundary of at most
deg(v) faces. Hence, we can isolate it with O(k + deg(v)) additional vertices
and edges. Since there are O(k 2 ) intersections in the pseudoline arrangement,
12

we can isolate all intersection vertices with O(k 2 (k + n)) additional edges
and vertices.
Now consider an aligned vertex v that is not an intersection vertex. In this
case v is incident to at most two cells and O(deg(v)) faces. We can isolate
all such vertices with O(n) additional vertices and edges. The same bound
holds for aligned edges.
3. Let f be a non-triangular face whose interior is intersected by a pseudoline L
and has no aligned edge and no aligned vertex on its boundary. Further, the
interior of f does not contain the intersection of two or more pseudolines.
Then the face f subdivides L into a set of pseudosegments S; see Fig. 9d.
We iteratively isolate such a pseudosegment S. Since f does not contain
the intersection of a set of pseudolines in its interior, there are two distinct
cells C 1 ∈ cells(Af ) and C 2 ∈ cells(Af ) with S on their boundary. Since f
neither contains an aligned vertex nor an aligned edge and G is biconnected,
there are exactly two edges e1 = vw and e2 = xy with the endpoints of S
in the interior of these edges and v, x and w, y on the boundaries of C 1 and
C 2 , respectively. Since f does not have an l-crossed edge, l ≥ 2, and every
1-crossed edge is 0-anchored, the vertices v, w, x, y are free vertices. We
construct a graph G0 by placing a vertex u on s and insert edges uv, uw, ux
uy, vx and wy. We route each edge so that it the interior of an edge does
not intersect the boundary of a cell C i . Thus, the edges vx and wy are free
and the others are 1-anchored and 0-crossed.
Every edge in f is at most 1-crossed, thus the number of pseudosegments is
linear in the size of G. Thus, we add only a number of vertices and edges
linear in the size of G.
4. If none of the cases above apply to a non-triangular face f , then neither the
interior nor the boundary of the face intersect a pseudoline Li . Thus, we can
triangulate f with a number of free edges linear in the size of f , i.e., in total
with O(k 4 n) edges.
Thus, in total there is an aligned triangulation (GT , A) of G whose size is in
O(k 4 n + k 2 (k + n) + n + k 4 n) = O(k 4 n).

Observe that the previous triangulation only uses the fact that every nontriangular face contains at most 1-crossed edges. While Lemma 5 is sufficient for
our purposes, for the sake of generality, we show how to isolate l-crossed edges.
This allows us to triangulate arbitrary aligned graphs without increasing the
alignment complexity.
Theorem 4. Every biconnected aligned graph (G, A) of alignment complexity
(l0 , l1 , l2 ) has an aligned triangulation (GT , A). The alignment complexity of
E(GT ) \ E(G) is (max{l0 , 1}, l1 , l2 ) and the size of this set is O(k 4 n).
Proof. For l ≥ 1, we iteratively isolate l-crossed edges uv from a non-triangular
face f as sketched in Fig. 10. Let C 0 , C 1 , . . . , C l ∈ cells(A) be the cells in f that
occur in this order along uv. If one of both vertices is free, say v, we place a new
vertex x in the interior of C l−1 . We insert the two edges ux, xv and route both
edges close to uv. This isolates the edge uv from f . Notice that the edge vx is
13

C1

Cl−1

x

Cl
v

u
Fig. 10: An l-crossed edge uv in a (grey) face f and a pseudoline arrangement
(blue). The green edges isolate the edge uv.

0-anchored and 1-crossed. In case that l0 ≥ 1, the alignment complexity of the
new aligned graph is (l0 , l1 , l2 ). Otherwise, the alignment complexity is (1, l1 , l2 ).
If u and v are aligned, we place x on the boundary of C l−1 and C l and route
the edges ux and vx as before. The alignment complexity is not affected by this
operation.
This procedure introduces a new (l − 1)-crossed edge. Repeating the process
l − 2 generates a new face f 0 from f where edge uv is substituted by a path of
at most 1-crossed edges. To isolate all l-crossed edge in (G, A), we add O(kn)
vertices and edges.
By isolating all l-crossed edges in this way, we obtain an aligned graph where
every non-triangular face is bounded by at most 1-crossed edges. Thus, we can
apply the methods used in the proof of Lemma 5 to triangulate (G, A) with
O(k 4 n) number of additional vertices and edges.

We now return to the treatment of aligned graphs with alignment complexity
(1, 0, ⊥). To simplify the proofs, we augment the input graph with an additional
cycle in the outer face that contains all intersections of A in its interior, and we
add subdivision vertices on the intersections of Li -aligned edges with pseudolines
Lj , i 6= j. A k-aligned graph is proper if (i) every aligned edge is 0-crossed, (ii) for
k ≥ 2, every edge on the outer face is 1-crossed, (iii) the boundary of the outer
face intersects every pseudoline exactly twice, and (iv) the outer face does not
contain the intersections of A.
An aligned graph (G0 , A) is a rigid subdivision of an aligned graph (G, A) if
and only if G0 is a subdivision of G and every subdivision vertex is an intersection
vertex with respect to A. We show that we can extend every k-aligned graph
(G, A) to a proper k-aligned triangulation (G0 , A).
Lemma 6. For k ≥ 2 and every k-aligned graph (G, A) of alignment complexity
(1, 0, ⊥), let (Grs , A) be a rigid subdivision of (G, A). Then there exists a proper
k-aligned triangulation (G0 , A) of alignment complexity (1, 0, ⊥) such that Grs
is a subgraph of G0 . The size of G0 is in O(k 4 n2 ). The set E(G0 ) \ E(G) has
alignment complexity (1, 0, ⊥) and does not contain aligned edges.
Proof. We construct a rigid subdivision (Grs , A) from (G, A) by placing subdivision vertices on the intersections of Li -aligned edges with pseudolines Lj , i 6= j.
14

We obtain a proper k-aligned triangulation (G0 , A) by embedding a simple cycle
C in the outer face of Grs and applying Lemma 4 and Lemma 5. In order to
construct C, we place a vertex vc in each unbounded cell c of A and connect two
vertices vc and vc0 if the cells c and c0 share a common boundary.

The following two lemmas show that we can reduce the size of the aligned
graph and obtain a drawing by merging two drawings or by unpacking an edge.
Lemma 7. Let (G, A) be a k-aligned triangulation. Let T be a separating triangle splitting G into subgraphs Gin , Gout so that Gin ∩Gout = T and Gout contains
the outer face of G. Then, (i) (Gout , A) and (Gin , A) are k-aligned triangulations,
and (ii) (G, A) has an aligned drawing if and only if there exists a common line
arrangement A such that (Gout , A) has an aligned drawing (Γout , A) and (Gin , A)
has an aligned drawing (Γin , A) with the outer face drawn as Γout [T ].
Proof. It is easy to verify that (Gout , A) and (Gin , A) are aligned triangulations.
An aligned drawing (Γ, A) of (G, A) immediately implies the existence of an
aligned drawing (Γout , A) of (Gout , A) and (Γin , A) of (Gin , A).
Let (Γout , A) be an aligned drawing of (Gout , A). Since (Γout , A) is an aligned
drawing, (Γout [T ], A) is an aligned drawing of (T, A). Let (Γin , A) be an aligned
drawing of (Gin , A) with the outer face drawing as Γout [T ]. Let Γ be the drawing
obtained by merging the drawing Γout and Γin . Since, (Γout , A) and (Γin , A) are
aligned drawings on the same line arrangement A, (Γ, A) is an aligned drawing
of (G, A).

Lemma 8. Let (G, A) be a proper k-aligned triangulation of alignment complexity (1, 0, ⊥) and let e be an interior 0-anchored aligned or an interior free
edge of G that does not belong to a separating triangle and is not a chord. Then
(G/e, A) is a proper k-aligned triangulation of alignment complexity (1, 0, ⊥).
Further, (G, A) has an aligned drawing if (G/e, A) has an aligned drawing.
Proof. We first prove that (G/e, A) is a proper k-aligned triangulation. Consider
a topological drawing of the aligned graph (G, A). Let c be the vertex in G/e
obtained from contracting the edge e = uv. We place c at the position of u.
Thus, all the edges incident to u keep their topological properties. We route the
edges incident to v close to the edge uv within the cell from which they arrive
to v in (G, A). Since e is not an edge of a separating triangle, G/e is simple and
triangulated.
Consider a free edge e. Observe that the triangular faces incident to e do not
contain an intersection of two pseudolines in their interior, since (G, A) does not
contain l-crossed edges, l ≥ 2. Therefore, (G/e, A) is an aligned triangulation.
Since e is not a chord, (G/e, A) is proper. Further, u and v lie in the interior of
the same cell, thus, the edges incident to c have the same alignment complexity.
If e is aligned, it is also 0-crossed, since (G, A) is proper. Since e is also
0-anchored, the triangles incident to e do not contain an intersection of two
pseudolines and therefore (G/e, A) is a proper aligned triangulation. The routing of the edges incident to c, as described above, ensures that the alignment
complexity is (1, 0, ⊥).
15

Nu

Nu

Nv

Nv

(a)

(b)

Fig. 11: Unpacking an edge in a drawing Γ 0 of G/e (a) to obtain a drawing Γ
of G (b).

Let (Γ 0 , A) be an aligned drawing of (G/e, A). We now prove that (G, A) has
an aligned drawing. Let Γ 00 denote the drawing obtained from Γ 0 by removing
c together with its incident edges and let f denote the face of Γ 00 where c used
to lie. Since G/e is triangulated and e is an interior edge and not a chord, f is
star-shaped and c lies inside the kernel of f ; see Fig. 11. We construct a drawing
Γ of G as follows. If one of vertices u and v lie on the outer face, we assume,
without loss of generality, that vertex to be u. First, we place u at the position
of c and insert all edges incident to u. This results in a drawing of the face f 0 in
which we have to place v. Since, u is placed in the kernel of f , f 0 is star-shaped.
If e is a free edge, the vertex v has to be placed in the same cell as u. We then
place v inside f 0 sufficiently close to c so that it lies inside the kernel of f 0 and
in the same cell as u. All edges incident to v are at most 1-crossed, thus, (Γ, A)
is an aligned drawing of (G, A).
Likewise, if e is an L-aligned edge, then v has to be placed on the corresponding to L line L ∈ A. In this case also c and therefore u lie on L. Since e is an
interior edge, there exist two triangles uv, vx, xu and uv, vy, yu sharing the edge
uv. Since, e is not part of a separating triangle, x and y are on different sides of
L. Therefore the face f 0 contains a segment of the line L of positive length that
is within the kernel of f 0 . Thus, we can place v close to u on the line L such that
the resulting drawing is an aligned drawing of (G, A).

4.2

One Pseudoline

We show that every 1-aligned graph (G, R) has an aligned drawing (Γ, R), where
R is a single pseudoline and R is the corresponding straight-line. Using the
techniques from the previous section, we can assume that (G, R) is a proper 1aligned triangulation. We show that unless G is very small, it contains a special
edge. This enables an inductive proof to construct an aligned drawing of (G, R).
16

x

f0

x

v

v

(a)

(b)

f

Fig. 12: Transformation from a red vertex (a) to a gray vertex (b).

Lemma 9. Let (G, R) be a proper 1-aligned triangulation without chords and
with k vertices on the outer face. If G is neither a triangle nor a k-wheel whose
center is aligned, then (G, R) contains an interior aligned or an interior free
edge.
Proof. We first prove two useful claims.
Claim 1. Consider the order in which R intersects the vertices and edges of G.
If vertices u and v are consecutive on R, then the edge uv is aligned.
Observe that the edge uv can be inserted into G without creating crossings.
Since G is a triangulation, it therefore contains uv, and further, since no 1-crossed
edge can have both its endpoints on R, it follows that indeed uv is aligned. This
proves the claim.
Claim 2. Let (G, R) be an aligned triangulation without aligned edges and let x
be an interior free vertex of G, then x is incident to a free edge.
Assume for a contradiction that all neighbors of x lie either on R or on the
other side of R. First, we slightly modify R to a curve R0 that does not contain
any vertices. Assume v is an aligned vertex; see Fig. 12. Since there are no aligned
edges, R enters v from a face f incident to v and leaves it to a different face f 0
incident to v. We then reroute R from f to f 0 locally around v. If v is incident
to x, we choose the rerouting such that it crosses the edge vx.
Notice that if an edge e is intersected by R in its endpoints, then R0 either
does not intersect it, or intersects it in an interior point. Moreover, e cannot be
intersected by R0 twice as in such case R would pass through both its endpoints.
Now, since G is a triangulation and the outer face of G is proper, R0 is a simple
cycle in the dual G? of G, and hence corresponds to a cut C of G. Let H denote
the connected component of G − C that contains x and note that all edges of
H are free. By the assumption and the construction of R0 , x is the only vertex
in H. Thus, R0 intersects only the faces incident to x which are interior. This
contradicts the assumption that R0 passes through the outer face of G. This
finishes the proof of the claim.
We now prove the lemma. Assume that G is neither a triangle nor a k-wheel
whose center is aligned. If G is k-wheel whose center is free, we find a free edge
17

by Claim 2. Otherwise, G contains at least two interior vertices. If one of both
vertices is free, we find a free edge by Claim 2. Otherwise, there is no free internal
vertex, therefore the only edge which can intersect R is a chord of G. Since G
does not contain any chord, there is a pair of aligned vertices consecutive along
R. Thus by Claim 1 the instance (G, R) has an aligned edge.

Theorem 5. Let (G, R) be a proper aligned graph and let (ΓO , R) be a convex
aligned drawing of the aligned outer face (O, R) of G. There exists an aligned
drawing (Γ, R) of (G, R) with the same line R and the outer face drawn as ΓO .
Proof. Given an arbitrary proper aligned graph (G, R), we first complete it to a
biconnected graph and then triangulate it by applying Lemma 4 and Lemma 5,
respectively.
We prove the claim by induction on the size of G. If G is just a triangle,
then clearly (ΓO , R) is the desired drawing. If G is the k-wheel whose center is
aligned, placing the vertex on the line in the interior of ΓO yields an aligned
drawing of G. This finishes the base case.
If G contains a chord e, then e splits (G, R) into two graphs G1 , G2 with
G1 ∩ G2 = e. It is easy to verify that (Gi , R) is an aligned graph. Let (ΓOi , R)
be a drawing of the face of ΓO ∪ e whose interior contains Gi . By the inductive
hypothesis, there exists an aligned drawing of (Γi , R) with the outer face drawn
as (ΓOi , R). We obtain a drawing Γ by merging the drawings Γ1 and Γ2 . The
fact that both (Γ1 , R) and (Γ2 , R) are aligned drawings with a common line R
implies that (Γ, R) is an aligned drawing of (G, R).
If G contains a separating triangle T , let Gin and Gout be the respective
split components with Gin ∩ Gout = T . By Lemma 7, the graphs (Gin , R) and
(Gout , R) are aligned graphs. By the induction hypothesis there exists an aligned
drawing (Γout , R) of the aligned graphs (Gout , R) with the outer face drawn as
(ΓO , R). Let Γ [T ] be the drawing of T in Γout . Further, (Gin , R) has by induction
hypothesis an aligned drawing with the outer face drawn as Γ [T ]. Thus, by
Lemma 7 we obtain an aligned drawing of (G, R) with the outer face drawn as
ΓO .
If G is neither a triangle nor a k-wheel, by Lemma 9, it contains an interior
aligned or an interior free edge e. Since e is not a chord and does not belong
to a separating triangle, by Lemma 8, (G/e, R) is an aligned graph and by the
induction hypothesis it has an aligned drawing (Γ 0 , R) with the outer face drawn
as ΓO . It thus follows by Lemma 8 again that (G, R) has an aligned drawing
with the outer face drawn as ΓO .

4.3

Alignment Complexity (1, 0, ⊥)

We now consider k-aligned graphs (G, A) of alignment complexity (1, 0, ⊥), i.e.,
every edge has at most one interior intersection and 2-anchored edges are forbidden. In this section, we prove that every such k-aligned graph has an aligned
drawing. As before we can assume that (G, A) is a proper aligned triangulation.
We show that if the structure of the graph is not sufficiently simple, it contains
18

Fig. 13: All possible variations of vertices and edges in Lemma 10.

a special edge. Further, we prove that every graph of this structure indeed has
an aligned drawing. Together this again enables an inductive proof that (G, A)
has an aligned drawing. Fig. 13 illustrates the statement of the following lemma.
Lemma 10. Let (G, A) be a proper k-aligned triangulation of alignment complexity (1, 0, ⊥) that neither contains a free edge, nor a 0-anchored aligned edge,
nor a separating triangle. Then (i) every intersection contains a vertex, (ii) every
cell of the pseudoline arrangement contains exactly one free vertex, (iii) every
pseudosegment is either covered by two aligned edges or intersected by a single
edge.
Proof. The statement follows trivially from the following sequence of claims. We
refer to an aligned vertex that is not an intersection vertex as a flexible aligned
vertex.
Claim 1. Every pseudosegment alternately intersects flexible aligned vertices and
edges.
Let S be a pseudosegment in the pseudoline arrangement A. As in the proof
of Lemma 9 one can argue that if two vertices occur consecutively along S, then
we find an aligned edge. Assume that S intersects two edges e1 , e2 consecutively
as depicted in Fig. 14a. Since G is a triangulation, it follows that e1 and e2 share
an endpoint v. Every 1-crossed edge in G is 0-anchored, thus all endpoints of e1
and e2 must be free. Further e1 and e2 are consecutive in the circular order of
edges around v as otherwise we would either find an intersection with S between
e1 and e2 or a free edge. Thus, e1 and e2 bound a face and are 1-crossed, hence
their endpoints distinct from v are in the same cell and connected by an edge
e, which is thus free. In a proper aligned graph, the edges on the outer face are
1-crossed, thus, e is an interior edge, contradicting our assumptions.
Claim 2. Every cell contains at least one free vertex.
Observe that every triangle T containing the intersection of two pseudolines
has at least one 2-anchored edge or one l-crossed edge, with l ≥ 2. Since by
definition (G, A) neither containst 2-anchored aligned edges, T cannot contain
an empty cell in its interior, i.e., a triangle of aligned edges. Further, since G is
proper, the outer face of G contains the intersection of every pair of pseudolines
19

u
e
e1
(a)

B

e2

v

y

x

v

w
(b)

(c)

(d)

Fig. 14: Illustrations for the proof Lemma 10.

in its interior. Thus, since G is triangulated every cell contains at least one
vertex.
Claim 3. Every cell contains at most one free vertex.
The following proof is similar to Claim 2 in the proof of Lemma 9. Let
C be a cell and assume for the sake of a contradiction that C contains more
than one vertex in its interior; see Fig. 14b. These vertices are connected by
edges to adjacent cells. If C contains a vertex v on its boundary, we reroute the
corresponding pseudolines close to v such that v is now outside of C; refer to
Fig. 14c. Let C 0 be the resulting cell, it represents a cut in the graph with two
components A and B, where C 0 contains B in its interior. It is not difficult to
see that the modified pseudolines are still pseudolines with respect to G. Since
(G, A) neither contains 2-anchored edges nor l-crossed edges, l ≥ 2, every edge
of (G, A0 ) intersects the boundary of C 0 at most once. Hence, B is connected
and since it contains at least two vertices it also contains at least one free edge,
contradicting our initial assumption.
Claim 4. Every flexible aligned vertex is incident to two 1-anchored aligned edges.
Let v be a vertex lying in the interior of a pseudosegment S. Let u and w
be the anchored vertices incident to S, see Fig. 14d. Further, let x and y be the
vertices in the interior of the two cells incident to S. Our instance (G, A) is triangulated and every edge is at most 1-crossed. Thus, the vertices u, x, w, y build
a quadrangle containing v in its interior. Since G does not contain a separating
triangles, it cannot contain the edge xy. Moreover, S contains exactly v in its
interior, otherwise we would find a free aligned edge. Finally, since (G, A) is an
aligned triangulation, the vertex v is connected to all four vertices and, thus
incident to two 1-anchored aligned edges.
Since (G, A) is an aligned triangulation, Property (iii) immediately follows
from Claims 3 and 4.

Lemma 11. Let (G, A) be a proper k-aligned triangulation of alignment complexity (1, 0, ⊥) that does neither contain a free edge, nor a 0-anchored aligned
edge, nor a separating triangle. Let A be a line arrangement homeomorphic to
the pseudoline arrangement A. Then (G, A) has an aligned drawing (Γ, A).
20

Proof. We obtain a drawing (Γ, A) by placing a free vertex in its cell, an aligned
vertex on its pseudosegment and an intersection vertex on its intersection. According to Lemma 10 every cell and every intersection contains exactly one
vertex and each pseudosegment is either crossed by an edge or it is covered by
two aligned edges. Observe that the union of two adjacent cells of the arrangement A is convex. Thus, this drawing of G has an homeomorphic embedding to
(G, A) and every edge intersects in (Γ, A) the line L ∈ A corresponding to the
pseudoline L ∈ A in (G, A)

The following theorem can be proven along the same lines as Theorem 5.
Theorem 6. Every k-aligned graph (G, A) of alignment complexity (1, 0, ⊥)
with a stretchable pseudoline arrangement A has an aligned drawing.
Proof. Let (G, A) be an arbitrary aligned graph, such that A is a stretchable
pseudoline arrangement, let denote by A the corresponding line arrangement.
By Lemma 6, we obtain a proper k-aligned triangulation (GT , A) that contains
a rigid subdivision of G as a subgraph. Assume that (GT , A) has an aligned
drawing (ΓT , A). Let (Γ 0 , A) be the drawing obtained from (ΓT , A) by removing
all subdivision vertices v and merging the two edges incident to v at the common
endpoint. Recall, that a subdivision vertex in a rigid subdivision of (G, A) lies on
an intersection in A. Hence the drawing (Γ 0 , A) is a straight-line aligned drawing
and contains an aligned drawing (Γ, A) of (G, A).
We now show that (GT , A) indeed has an aligned drawing. We prove this
by induction on the size of the instance (GT , A). If (GT , A) neither contains
a free edge, nor a 0-anchored aligned edge, nor a separating triangle, then, by
Lemma 11 there is an aligned drawing (ΓT , A).
If G contains a separating triangle T , let Gin and Gout be the respective split
components with Gin ∩ Gout = T . Since the alignement complexity of (G, A)
is (1, 0, ⊥), triangle T is intersected by most one pseudoline L. It follows that,
(Gout , A) is a k-aligned triangulation and that (Gin , L) is a 1-aligned triangulation. By the induction hypothesis there exists an aligned drawing (Γout , A) of
(Gout , A). Let Γout [T ] be the drawing of T in Γout . By Theorem 5, we obtain an
aligned drawing (Γin , L) with T drawn as Γout [T ]. Moreover, since the drawing
of T is fixed and is intersected only by line L, (Γin , A) is an aligned drawing.
Thus, according to Lemma 7, there exists an aligned drawing of (G, A).
If GT does not contain separating triangles but contains either a free edge
or a 0-anchored aligned edge e, let GT /e be the graph after the contraction
of e. Observe that, since (GT , A) is proper, every edge on the outer face is 1crossed, and therefore every chord is `-crossed, ` ≥ 1. Thus, e is an interior
edge of (GT , A) and is not a chord. Thus, by Lemma 8, (GT /e, A) is a proper
aligned triangulation. By induction hypothesis, there exists an aligned drawing
of (GT /e, A), and thus, by the same lemma, there exists an aligned drawing of
(GT , A).

21

Fig. 15: Sketch of a 2-aligned triangulation without aligned or free edges. The
triangulation can be completed as indicated by the black edges.

5

Conclusion

In this paper we showed that if A is stretchable, then every k-aligned graph
(G, A) of alignment complexity (1, 0, ⊥) has a straight-line aligned drawing. As
an intermediate result we showed that a 1-aligned graph (G, R) has an aligned
drawing with a fixed convex drawing of the outer face. We showed that the less
restricted version of this problem, where we are only given a set of vertices to
be aligned, is N P-hard but fixed-parameter tractable.
The case of more general alignment complexities is widely open. Our techniques imply the existence of one-bend aligned drawings of general 2-aligned
graphs [13]. However, the existence of straight-line aligned drawings is unknown
even if in addition to 1-crossed edges, we only allow 2-anchored edges, i.e., in the
case of alignment complexity (1, 0, 0). In particular, there exist 2-aligned graphs
that neither contain a free edge nor an aligned edge but their size is unbounded
in the size of the arrangement; see Fig. 15. It seems that further reductions are
necessary to arrive at a base case that can easily be drawn. This motivates the
following questions.
1) What are all the combinations of line numbers k and alignment complexities
C such that for every k-aligned graph (G, A) of alignment complexity C there
exists a straight-line aligned drawing provided A is stretchable.
2) Given a k-aligned graph (G, A) and a line arrangement A homeomorphic to
A, what is the complexity of deciding whether (G, A) admits a straight-line
aligned drawing (Γ, A)?

References
1. T. C. Biedl, M. Kaufmann, and P. Mutzel. Drawing planar partitions II: HHdrawings. In J. Hromkovič and O. Sýkora, editors, WG’98, pages 124–136. Springer,

22

1998.
2. J. Cano, C. D. Tóth, and J. Urrutia. Upper bound constructions for untangling
planar geometric graphs. SIAM Journal on Discrete Mathematics, 28(4):1935–
1943, 2014.
3. S. Chaplick, K. Fleszar, F. Lipp, A. Ravsky, O. Verbitsky, and A. Wolff. Drawing
graphs on few lines and few planes. In Y. Hu and M. Nöllenburg, editors, GD’16,
pages 166–180. Springer, 2016.
4. S. Chaplick, K. Fleszar, F. Lipp, A. Ravsky, O. Verbitsky, and A. Wolff. The complexity of drawing graphs on few lines and few planes. In F. Ellen, A. Kolokolova,
and J.-R. Sack, editors, Algorithms and Data Structures: 15th International Symposium, WADS 2017, pages 265–276. Springer, 2017.
5. G. Da Lozzo, V. Dujmović, F. Frati, T. Mchedlidze, and V. Roselli. Drawing planar
graphs with many collinear vertices. In Y. Hu and M. Nöllenburg, editors, GD’16,
pages 152–165. Springer, 2016.
6. V. Dujmović. The utility of untangling. In E. Di Giacomo and A. Lubiw, editors,
GD’15, pages 321–332. Springer, 2015.
7. V. Dujmović, W. Evans, S. Kobourov, G. Liotta, C. Weibel, and S. Wismath. On
graphs supported by line sets. In U. Brandes and S. Cornelsen, editors, GD’10,
pages 177–182. Springer, 2011.
8. V. Dujmović and S. Langerman. A center transversal theorem for hyperplanes and
applications to graph drawing. Discrete & Computational Geometry, 49(1), 2013.
9. U. Fößmeier and M. Kaufmann. Nice drawings for planar bipartite graphs. In
Algorithms and Complexity, Third Italian Conference, CIAC ’97, pages 122–134,
1997.
10. M. R. Garey, D. S. Johnson, and R. Tarjan. The planar Hamiltonian circuit
problem is NP-complete. SIAM Journal on Computing, 5(4):704–714, 1976.
11. J. E. Goodman and R. Pollack. Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines. Journal of Combinatorial Theory,
Series A, 29(3):385 – 390, 1980.
12. F. Levi. Die Teilung der projektiven Ebene durch Geraden oder Pseudogerade.
Ber. Math.-Phys. Kl. Sächs. Akad. Wiss, 78:256–267, 1926.
13. T. Mchedlidze, M. Radermacher, and I. Rutter. Aligned drawings of planar graphs.
In Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017), 2017.
14. N. E. Mnëv. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In O. Y. Viro and A. M. Vershik,
editors, Topology and Geometry — Rohlin Seminar, volume 1346 of LNCS, pages
527–543. Springer, 1988.
15. P. Shor. Stretchability of pseudolines is NP-hard. In Applied Geometry and Discrete
Mathematics–The Victor Klee Festschrift, volume 4 of DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, pages 531–554. Amer. Math. Soc.,
1991.
16. M. Wahlström. Abusing the Tutte matrix: An algebraic instance compression for
the K-set-cycle problem. In 30th International Symposium on Theoretical Aspects
of Computer Science, STACS 2013, pages 341–352, 2013.

23

