Steven Chaplick

Thomas C Van Dijk

Myroslav Kryven
email: myroslav.kryven@uni-wuerzburg.de

Ji-Won Park

Alexander Ravsky
email: alexander.ravsky@uni-wuerzburg.de

Alexander Wolff

Bundled Crossings Revisited

An effective way to reduce clutter in a graph drawing that has (many) crossings is to group edges that travel in parallel into bundles. Each edge can participate in many such bundles. Any crossing in this bundled graph occurs between two bundles, i.e., as a bundled crossing. We consider the problem of bundled crossing minimization: A graph is given and the goal is to find a bundled drawing with at most k bundled crossings. We show that the problem is NP-hard when we require a simple drawing. Our main result is an FPT algorithm (in k) for simple circular layouts where vertices must be placed on a circle and edges must be drawn inside the circle. These results make use of the connection between bundled crossings and graph genus. We also consider bundling crossings in a given drawing, in particular for storyline visualizations.

Introduction

In traditional node-link diagrams, vertices are mapped to points in the plane and edges are usually drawn as straight-line segments connecting the vertices. For large and dense graphs, however, such layouts tend to be so cluttered that it is hard to see any structure in the data. For this reason, Holten [START_REF] Holten | Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data[END_REF] introduced bundled drawings, where edges that are close together and roughly go into the same direction are drawn using Bézier curves such that the grouping becomes visible. Due to the practical effectiveness of this approach, it has quickly been adopted by the InfoVis community [START_REF] Cui | Geometry-based edge clustering for graph visualization[END_REF][START_REF] Gansner | Multilevel agglomerative edge bundling for visualizing large graphs[END_REF][START_REF] Hurter | Bundled visualization of dynamicgraph and trail data[END_REF][START_REF] Hurter | Graph bundling by kernel density estimation[END_REF][START_REF] Pupyrev | Edge routing with ordered bundles[END_REF]. However, bundled drawings have only recently attracted study from a theoretical point of view [START_REF] Alam | The bundled crossing number[END_REF][START_REF] Fink | Bundled crossings in embedded graphs[END_REF][START_REF] Fink | Ordering metro lines by block crossings[END_REF][START_REF] Van Dijk | Block crossings in storyline visualizations[END_REF].

Crossing minimization is a fundamental problem in graph drawing [START_REF] Schaefer | The graph crossing number and its variants: A survey[END_REF]. Its natural generalization in bundled drawings is bundled crossing minimization, see Definition 1 for the formalization of a bundled crossing. In his survey on crossing minimization, Schaefer lists the bundled crossing number as a variant of the crossing number and suggests to study it [32, page 35].

Related Work. Fink et al. [START_REF] Fink | Ordering metro lines by block crossings[END_REF] considered bundled crossings (which they called block crossings) in the context of drawing metro maps. A metro network is a planar graph where vertices are stations and metro lines are simple paths in this graph. These paths representing metro lines can share edges. They enter an edge at one endpoint in some linear order, follow the edge as x-monotone curves (considering the edge as horizontal), and then leave the edge at the other endpoint in some linear order. In order to improve the readability of metro maps, the authors suggested to bundle crossings. The authors then studied the problem of minimizing bundled crossings in such metro maps. Fink et al. also introduced monotone bundled crossing minimization where each pair of lines can intersect at most once. Later, Fink et al. [START_REF] Van Dijk | Block crossings in storyline visualizations[END_REF] applied the concept of bundled crossings to drawing storyline visualizations. A storyline visualization is a set of x-monotone curves where the x-axis represents time in a story. Given a set of meetings (subsets of the curves that must be consecutive at given points in time), the task is to find a drawing that realizes the meetings and minimizes the number of bundled crossings. Fink et al. showed that, in this setting, minimizing bundled crossings is fixed-parameter tractable (FPT) in the number of curves and can be approximated in a restricted case. Van Dijk et al. [START_REF] Van Dijk | Computing storylines with few block crossings[END_REF] gave ILP and SAT formulations of the problem and evaluated these experimentally.

Our research builds on recent works of Fink et al. [START_REF] Fink | Bundled crossings in embedded graphs[END_REF] and Alam et al. [START_REF] Alam | The bundled crossing number[END_REF], who extended the notion of bundled crossings from sets of x-monotone curves to general drawings of graphs. We discuss their results in more detail soon.

The degenerate crossing number is defined by allowing more than two edges to intersect at the same point; several variants (one of which is also called the genus crossing number) have been studied [START_REF] Ackerman | On the degenerate crossing number[END_REF][START_REF] Mohar | The genus crossing number[END_REF][START_REF] Pach | Degenerate crossing numbers[END_REF][START_REF] Schaefer | The degenerate crossing number and higher-genus embeddings[END_REF]. The degenerate crossing number and the bundled crossing number might look completely different, but it turns out that the degenerate crossing number is closely related to the nonorientable genus [START_REF] Mohar | The genus crossing number[END_REF] while the bundled crossing number is closely related to the orientable genus as we will see. In graph drawing, it is common to define a drawing of a graph as a function that maps vertices to distinct points in the plane and edges to Jordan arcs that connect the corresponding points. In this paper, we are less restrictive; we sometimes allow edges to self-intersect. However, we forbid any three edges to share the same point. We will often identify vertices with their points and edges with their curves. Moreover, we assume that each pair of edges shares at most a finite number of points, that edges can touch (that is, be tangent to) each other only at endpoints, and that any point of the plane that is not a vertex is contained in at most two edges. A drawing is simple if any two edges intersect at most once and no edge self-intersects. We consider both simple and non-simple drawings; look ahead at Fig. 2 for a simple and a non-simple drawing of K 3,3 .

Definition 1 (Bundled Crossing) Let D be a drawing, not necessarily simple, and let I(D) be the set of intersection points among the edges (not including the vertices) in D. We say that a bundling of D is a partition of I(D) into bundled crossings, where a set B ⊆ I(D) is a bundled crossing if the following holds (see Fig. 1).

• B is contained in a closed region R(B) of the plane whose boundary consists of four Jordan arcs ẽ1 , ẽ2 , ẽ3 , and ẽ4 that are pieces of edges e 1 , e 2 , e 3 , and e 4 in D (with ẽi = e i ∩ R(B) for i ∈ {1, 2, 3, 4}).

• The pieces of the edges cut out by the region R(B) can be partitioned into two sets Ẽ1 and Ẽ2 such that ẽ1 , ẽ3 ∈ Ẽ1 , ẽ2 , ẽ4 ∈ Ẽ2 , and each pair of edge pieces in Ẽ1 × Ẽ2 has exactly one intersection point in R(B), whereas no two edge pieces in Ẽ1 intersect and no two edge pieces in Ẽ2 intersect.

Our definition is similar to that of Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] but defines the Jordan region R(B) more precisely. We call the sets Ẽ1 and Ẽ2 of edge pieces bundles and the Jordan arcs ẽ1 , ẽ3 ∈ Ẽ1 and ẽ2 , ẽ4 ∈ Ẽ2 frame arcs of the bundles Ẽ1 and Ẽ2 , respectively. For simple drawings, we accordingly call the edges that bound the two bundles of a bundled crossing frame edges. We say that a bundled crossing is degenerate if at least one of the bundles consists of only one edge piece; see Fig. 1b. In this case, the region of the plane associated with the crossing coincides with that edge piece. In particular, any point in I(D) by itself is a degenerate bundled crossing. Hence, every drawing admits a trivial bundling.

We use bc(G) to denote the bundled crossing number of a graph G, i.e., the smallest number of bundled crossings over all bundlings of all simple drawings of G. When we do not insist on simple drawings, we denote the corresponding number by bc (G). In the circular setting, where vertices are required to lie on the boundary of a disk and edges inside this disk, we consider the analogous circular bundled crossing numbers bc • (G) and bc • (G) of a graph G. If, in addition, the vertices are required to be in a prescribed circular order π, we consider the circular bundled crossing number with a fixed vertex order π and denote this number as bc • (G, π). (In the literature on book embeddings, circular layouts are commonly called 1-page (book) layouts, but since we do not consider more than one page here, we follow previous literature [START_REF] Alam | The bundled crossing number[END_REF][START_REF] Fink | Bundled crossings in embedded graphs[END_REF] on the bundled crossing number and stick to the term circular.)

By bc(G, D) we denote the bundled crossing number of a specific simple drawing D of G. We say fixed drawing for this case. Similarly, by bc (G, D) we denote the bundled crossing number of a specific, not necessarily simple drawing D of a graph G. By bc • (G, D) we denote the bundled crossing number of a simple circular drawing D of a graph G. As Fink et al. [START_REF] Fink | Bundled crossings in embedded graphs[END_REF] observed1 in this variant of the problem, we can assume the graph to be a matching.

Fink et al. [START_REF] Fink | Bundled crossings in embedded graphs[END_REF] showed that it is NP-hard to compute the minimum number bc(G, D) of bundled crossings that a given drawing D of a graph G can be partitioned into. They also showed that this problem generalizes the problem of partitioning a rectilinear polygon with holes into the minimum number of rectangles, and they exploited this connection to construct a 10-approximation for computing the number bc • (G, D) of bundled crossings in the case of a circular drawing. They left open the computational complexity of the general and the circular bundled crossing number for the case that the drawing is not fixed.

Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] showed that bc (G) equals the orientable genus of G, which in general is NP-hard to compute [START_REF] Thomassen | The graph genus problem is NP-complete[END_REF]. They also showed that there is a graph G with bc (G) = bc(G) by proving that bc (K 6 ) = 1 < bc(K 6 ). As it turns out, the two problem variants differ in the circular setting, too (see Fig. 2 and Observation 2). For computing bc(G) and bc • (G), Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] gave an algorithm whose approximation factor depends on the density of the graph. They posed the existence of an FPT algorithm for bc • (G) as an open question.

Our Contribution. As some graphs G have bc (G) = bc(G) (see Fig. 2), Fink et al. [START_REF] Fink | Bundled crossings in embedded graphs[END_REF] posed the complexity of computing the bundled crossing number bc(G) of a given graph G as an open problem. We settle this in Section 2 as follows:

Theorem 1 Given a graph G, it is NP-hard to compute bc(G).

Our main result, which we prove in Section 3, resolves an open question of Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] concerning the fixed-parameter tractability of bundled crossing minimization in circular layouts as follows:

Theorem 2 There is a computable function f such that, for any n-vertex graph G and integer k, we can check, in O(f (k)n) time, whether bc • (G) ≤ k, i.e., whether G admits a circular layout with k bundled crossings. Within the same time bound, such a layout can be computed.

To prove this, we use an approach similar to that of Bannister and Eppstein [START_REF] Bannister | Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth[END_REF] for 1-page crossing minimization (that is, edge crossing minimization in a circular layout). Bannister and Eppstein observe that the set of crossing edges of a circular layout with k edge crossings of a graph G forms an arrangement of curves that partition the drawing into O(k) subgraphs, each of which occurs in a distinct face of this arrangement. The subgraphs are obviously outerplanar. This means that G has bounded treewidth. So, by enumerating all ways to draw the crossing edges of a circular layout with k edge crossings, and, for each such way, expressing the edge partition problem (into crossing edges and outerplanar components) in extended monadic second order logic (MSO 2 ), Courcelle's Theorem [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF] (stated as Theorem 5 in Section 3) can be applied (leading to fixed-parameter tractability).

The difficulty in using this approach for bundled crossing minimization is in showing how to partition the graph into a set of O(k) "crossing edges" (our analogy will be the frame edges) and a collection of O(k) outerplanar graphs. This is where we exploit the connection to genus. Moreover, constructing an MSO 2 formula is somewhat more difficult in our case due to the more complex way our regions interact with our special set of edges.

Again using the above-mentioned connection, here between genus and the circular bundled crossing number bc • , we can decide whether bc • (G) = k in 2 O(k) n time. In other words, if non-simple drawings are allowed, the problem is also FPT in k; see Section 3 (Theorem 4).

We also consider the setting where we are given a drawing and the task is to bundle the existing edge crossings into as few bundled crossings as possible, that is, computing bc(G, D) for a given drawing D of a graph G. We show in Section 4 that we can use an algorithm of Marx

(G, π) ≤ k in 2 O(k 2 ) + O(m) time, improving on an 2 O(k 2 log k) + O(m) -time algorithm of Alam et al. [2]
In Section 5 we consider storyline visualizations. In contrast to the above results, the storyline literature considers the number of characters m to be small and the number of crossings to be large. (Recall that storyline visualizations Table 1: Algorithmic and complexity results concerning bundled crossing minimization for an m-edge graph G with restrictions such as vertex order π, drawing D, edge density δ, and k bundled crossings. We omit polynomial terms, and ϕ is the golden ratio. Our results are in boldface.

General layout

Circular layout bc(G)

6δ δ-3 -approx. for δ>3 [2] bc • (G) 6δ δ-2 -approx. for δ>2 [2] NP-hard (Thm. 1) FPT (Thm. 2) bc (G) NP-hard [16] bc • (G) FPT: 2 O(k) (Thm. 4) bc(G, D) NP-hard [16] bc • (G, D) 10-approximation [16] XP: m O( √ k) (Thm. 6(b)) FPT: k O( √ k) (Thm. 6(c)) bc (G, D) XP: c O( √ k) (Thm. 6(a)) Storyline layout bc • (G, π) 16-approx., FPT: k O(k 2 ) [2] bc s (D) FPT: ϕ 2m (Thm. 8) FPT: 2 O(k 2 ) (Thm. 6(d))
are non-simple.) We show that computing the bundled crossing number bc s (D) of a given storyline visualization D can be done in O(ϕ 2m poly(m + c)) time, where c is the number of crossings in D and ϕ is the golden ratio. Note that this is fixed parameter tractable in m.

For an overview of existing and new results see Table 1.

Computing bc(G) Is NP-Hard

For a given graph G, finding a drawing with the fewest bundled crossings resembles computing the orientable genus2 g(G) of G. In fact, Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] showed that bc (G) = g(G). Thus, deciding whether bc (G) = k for some k is NP-hard and FPT in k since the same holds for deciding whether g(G) = k [START_REF] Kawarabayashi | A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width[END_REF][START_REF] Mohar | A linear time algorithm for embedding graphs in an arbitrary surface[END_REF][START_REF] Thomassen | The graph genus problem is NP-complete[END_REF].

Theorem 3 ([2]
) For every graph G with genus k, it holds that bc (G) = k.

To show this, Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] first showed that a drawing with k bundled crossings can be lifted onto a surface of genus k, and thus bc (G) ≥ g(G):

Observation 1 ([2]
) A drawing D with k bundled crossings can be lifted onto a surface of genus k via a one-to-one correspondence between bundled crossings and handles, i.e., at each bundled crossing, we attach a handle for one of the two edge bundles, thus providing a crossing-free lifted drawing; see Fig. 8.

Then, to see that bc (G) ≤ g(G), Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] used the fundamental polygon representation (or polygonal schema) [START_REF] De Verdière | Computational topology of graphs on surfaces[END_REF] of a drawing on a genus-g surface. More precisely, the sides of the polygon are numbered in circular order a 1 , b 1 , a 1 , b 1 , . . . , a g , b g , a g , b g ; for 1 ≤ k ≤ g, the pairs (a k , a k ) and (b k , b k ) of sides are identified in opposite direction, meaning that an edge leaving side a k appears on the corresponding position of side a k ; see Fig. 3 and Fig. 4a for an example showing K 6 drawn in a fundamental square, which models a drawing on the torus. In such a representation, all vertices lie in the interior of the fundamental polygon and all edges leave the polygon avoiding vertices of the polygon. Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] showed that such a representation can be transformed into a nonsimple bundled drawing with g many bundled crossings. It is not clear, however, when such a representation can be transformed into a simple bundled drawing with g bundled crossings, as this transformation can produce drawings with self-intersecting edges and pairs of edges crossing multiple times, e.g., Alam et al. [2, Lemma 1] showed that bc(K 6 ) = 2 while bc (K 6 ) = g(K 6 ) = 1.

We now show that computing the bundled crossing number remains NP-hard for simple drawings.

Proof of Theorem 1: Let G be the graph obtained from G by subdividing each edge O(|E(G)| 2 ) times. We reduce from the NP-hardness of computing the genus g(G) of G by showing that bc(G ) = g(G), with Observation 1 in mind.

Consider the embedding of G onto the genus-g(G) surface. By a result of Lazarus et al. [24, Theorem 1], we can construct a fundamental polygon representation of the embedding so that its boundary intersects with edges of the graph O(g(G)|E(G)|) times. Note that each edge piece outside the polygon between the sides of the polygon (a k , a k ) intersects each other edge piece outside the polygon between the sides of the polygon (b k , b k ) at most once and does not have any other intersection points; see Fig. 3. We then subdivide the edges by adding a vertex to each intersection of an edge with the boundary of the fundamental polygon. This process of subdividing edges ensures that no edge intersects itself or intersects another edge more than once in the corresponding drawing of the graph on the plane; hence, the drawing is simple. Since g(G) ≤ |E(G)|, by subdividing edges further whenever necessary, we obtain a drawing of G . Our subdivisions keep the integrity of all bundled crossings, so bc(G ) ≤ g(G). On the other hand, since subdividing edges does not affect the genus, g(G) = g(G ) = bc (G ) ≤ bc(G ).

Computing bc • (G) and bc • (G) Is FPT

We now consider circular layouts, where vertices are placed on a circle and edges are routed inside the circle. We note that bc • (G) and bc • (G) can be different.

Observation 2 bc • (K 3,3 ) = 1 but bc • (K 3,3 ) > 1.
Proof: Let V (K 3,3 ) = {a, b, c} ∪ {a , b , c }. A drawing with bc • (K 3,3 ) = 1 is obtained by placing the vertices a, a , b, b , c, c in clockwise order around a circle; see Fig. 2b. If a graph G has bc • (G) = 1 then G is planar because we can embed edges for one bundle outside the circle. Hence, bc Similarly to computing bc (G), we compute bc • (G) via computing genus. To show this we first prove the following.

• (K 3,3 ) > 1. JGAA, 0(0) 0-0 (0) 7 a b c c a b (a) a a b b c c (b) Figure 2: bc • (K 3,3 ) = bc • (K 3,3 ); see Observation 2 a k a k b k b k
Lemma 1 Given a graph G = (V, E), let G be the graph obtained from G by adding a new vertex v adjacent to every vertex of G. Then bc • (G) = g(G ).

Proof: Similarly as in [2, Theorem 1], it is easy to see that bc • (G) is an upper bound for the genus of G , because, according to Observation 1, we can lift any circular drawing of G onto a surface S of genus bc • (G) and then we can add v using the outside of the circle. Clearly, this produces a crossing-free drawing of G on the surface S.

It remains to show that given a crossing-free drawing of G on a surface of genus k, we can construct a circular drawing of G with at most k bundled crossings. Consider a drawing of G on a surface S of genus k.

We use the fundamental polygon representation [2, Theorem 1] to the drawing of G on the surface S of genus k; see Fig. 4a. Then we modify this representation so that all the neighbors N (v ) of v in G are placed in anneighborhood of v . We now explain the modification in more detail. Consider all the edges incident to v in the representation and drag each neighbor u of v along the edge uv (as illustrated in Fig. 4b) until it reaches the -neighborhood N (v ) of v . Since for each u ∈ N (v ) the edges uw ∈ E with w = v are bundled together at the position where u was in the representation and dragged together with u along the edge uv , this does not change the number of bundled crossings.

Since all the vertices are located on the boundary of the -neighborhood of v in the modified representation, all the edges between v and V \ v are drawn inside the polygon. After removing the vertex v from the representation, we obtain a circular drawing of G with at most k bundled crossings.

Theorem 4 Testing whether bc

• (G) = k can be done in 2 k O(1) n time. Proof: By Lemma 1, bc • (G) = g(G )
, where G is a graph with a vertex v adjacent to every vertex of G. Applying the 2 g O( 1) n -time algorithm for computing genus [START_REF] Kawarabayashi | A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width[END_REF] completes the proof.

To prove our main result (Theorem 2) we develop an algorithm that tests whether bc • (G) = k in FPT time with respect to k. Our algorithm is inspired by recent works on circular layouts with at most k crossings [START_REF] Bannister | Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth[END_REF] and circular layouts where each edge is crossed at most k times [START_REF] Chaplick | Beyond outerplanarity[END_REF]. In both of these prior works, it is first observed that the graphs admitting such circular layouts have treewidth O(k), and then algorithms are developed using Courcelle's theorem, which establishes that expressions in MSO 2 logic can be evaluated efficiently. (The basic definition of treewidth is included below; we defer formalizing MSO 2 logic to Section 3.4 where we additionally construct our needed formulas.) Theorem 5 (Courcelle [START_REF] Courcelle | The monadic second-order logic of graphs. I. Recognizable sets of finite graphs[END_REF][START_REF] Courcelle | Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach[END_REF]) For any integer t ≥ 0 and any MSO 2 formula ψ of length , an algorithm can be constructed which takes a graph G with n vertices, m edges, and treewidth at most t and decides in O(f (t, ) • (n + m)) time whether G |= ψ where the function f from this time bound is a computable function of t and .

We proceed along the lines of Bannister and Eppstein [START_REF] Bannister | Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth[END_REF], who used a similar approach to show that edge crossing minimization in a circular layout is in FPT (as mentioned in the introduction). We start by very carefully describing a surface (in the spirit of Observation 1) onto which we will lift our drawing. We will then examine the structure of this surface (and our algorithm) for the case of one bundled crossing and finally for k bundled crossings.

Treewidth The concept of treewidth was introduced by Bertelé and Brioschi [START_REF] Bertelè | Nonserial dynamic programming[END_REF] and then later rediscovered (and popularized) by Robertson and Seymour [START_REF] Robertson | Graph minors. III. Planar tree-width[END_REF]. A tree decomposition of a graph G is a pair (X, T ), where T is a tree and

X = {X i | i ∈ V (T )} is a family of subsets of V (G), called bags, such that (1) for all v ∈ V (G), the set of nodes T v = {i ∈ V (T ) | v ∈ X i } induces a non- empty connected subtree of T , and (2) for each edge uv ∈ E(G) there exists i ∈ V (T ) such that both u and v are in X i . The maximum of |X i | -1, i ∈ V (T ),
is called the width of the tree decomposition. The treewidth, tw(G), of a graph G is the minimum width over all tree decompositions of G. For our purposes, an important fact is that every outerplanar graph G has tw(G) ≤ 2 [START_REF] Mitchell | Linear algorithms to recognize outerplanar and maximal outerplanar graphs[END_REF]. An easy observation is that, for any graph G, adding one vertex to G increases its treewidth by at most one, e.g., we simply add this new vertex to every bag of an optimal tree decomposition of G. A direct consequence is that that adding t vertices increases the treewidth by at most t.

Constructing the Surface Determined by a Bundled Drawing

Consider a bundled circular drawing D. Note that adding parallel edges to the drawing (i.e., making our graph a multi-graph) allows us to assume that every bundled crossing has four distinct frame edges and can be done without modifying the number of bundled crossings; see Fig. 8. Each bundled crossing B defines a Jordan curve made up of the four Jordan arcs ẽ1 , ẽ2 , ẽ3 , ẽ4 in clockwise order taken from its four frame edges e 1 , . . . , e 4 , respectively, where (e 1 , e 3 ) and (e 2 , e 4 ) frame the two bundles and e i = v 2i-1 v 2i . Similarly to Observation 1, we can construct a surface S by creating a flat handle (note that this differs from the usual definition of a handle since our flat handles have a boundary) on top of D which connects ẽ2 to ẽ4 and doing so for each bundled crossing.

We then lift the drawing D onto S by rerouting the edges of one of the bundles over its corresponding handle for each bundled crossing B obtaining the lifted drawing D S . To avoid the crossings in D S of the frame edges that can occur at the foot of the handle of B, we can make the handle a bit wider and add corner-cuts (as illustrated in Fig. 5b) to preserve the topology of the surface. Thus, D S is crossing-free. We now cut S into components (maximal connected subsets) along the frame edges and corner-cuts of each bundled crossing, resulting in a subdivision Ω of S.

We use D Ω to denote the sub-drawing of D S on Ω, i.e., D Ω is missing the frame edges since these have been cut out. We now consider the components of Ω. Notice that every edge of D Ω is contained in one component of Ω. In order for a component s of Ω to contain an edge e of D Ω , s must have both endpoints of e on its boundary. With this in mind we focus on certain components of Ω. Namely, we call a component a region if it contains a vertex of G on its boundary. Observe that a crossing in D which does not involve a frame edge corresponds, in D Ω , to a pair of edges where one goes over a handle and the other goes underneath.

Recognizing a Graph with One Bundled Crossing

We now discuss how to recognize if an n-vertex graph G = (V, E) can be drawn in a circular layout with one bundled crossing. Consider a bundled circular drawing D of G consisting of one bundled crossing. The bundled crossing consists of two bundles, which are bounded by the set F = {e 1 , e 2 , e 3 , e 4 } of frame edges. By V (F ) we denote the set of vertices incident to frame edges. Via the construction above, we obtain the subdivided surface Ω; see Fig. 5. Let r 1 and r 2 be the regions that are each bounded by a pair of frame edges corresponding to one of the bundles, and let r 3 , . . . , r 6 be the regions each bounded by one edge from one pair and one from the other pair; see Fig. 5b. These are all the regions of Ω. Since, as mentioned before, each of the non-frame edges of G (i.e., each e ∈ E(G) \ F ) along with its two endpoints is contained in exactly one of these regions, each component of G \ V (F ) and each edge connecting it to vertices of V (F ) is drawn in D Ω in some region of Ω. In this sense, for each region r of Ω, we use G r to denote the subgraph of G induced by the components of G \ V (F ) contained in r and the edges connecting them to vertices in V (F ). Additionally, each vertex of G is either incident to an edge in F (in which case it is on the boundary of at least two regions) or it is on the boundary of exactly one region.

v 4 v 8 v 3 v 7 v 1 v 5 v 2 v 6 e 3 e 1 e 4 e 2 (a)
v 4 v 8 v 3 v 7 v 1 v 5 r 3 r 4 r 5 r 6 r 2 v 2 v 6 r 1 (b) b 1 b 2 h v 4 v 8 v 3 v 7 v 1 v 5 v 2 v 6 r 1 e 3 e 1 (c) v 4 v 8 v 3 v 7 v 1 v 5 v 2 v 6 b h r 3 (d)
Note that there are two types of regions: those in {r 1 , r 2 } and those in {r 3 , r 4 , r 5 , r 6 }. Consider a region of the first type, say r 1 ; see Fig. 5b. Observe that G r1 is outerplanar. Moreover, G r1 has a special outerplanar drawing where, on the boundary of r 1 , we see (in clockwise order) the frame edge e 1 , the vertices mapped to the (v 1 , v 5 )-arc, the frame edge e 3 , and then the vertices mapped to the (v 6 , v 2 )-arc. We now describe how to augment G r1 to a planar graph G * r1 where in every planar embedding of G * r1 the sub-embedding of G r1 has this special outerplanar form 3 . The vertex set of

G * r1 is V (G r1 ) ∪ {h, b 1 , b 2 }
where we call h hub vertex and b 1 and b 2 boundary vertices (one for each arc of the boundary of r 1 to which vertices can be mapped); see Fig. 5c. The graph G * r1 has four types of edges; the edges in E(G r1 ), edges that make h the hub of a wheel whose cycle is

C = (v 6 , b 2 , v 2 , v 1 , b 1 , v 5 , v 6 )
, edges from b 1 to the vertices on the (v 1 , v 5 )-arc, and edges from b 2 to the vertices on the (v 6 , v 2 )-arc (both including the endpoints). Clearly, we can obtain a planar embedding of G * r1 by drawing the elements of G * r1 \ G r1 "outside" of the outerplanar drawing of G r1 described before. Moreover, every planar embedding of G * r1 contains an outerplanar embedding of G r1 that can be drawn in the special form needed to "fit" into r 1 , in the sense that all of G r1 lies (or can be put) inside the simple cycle C. (For example, if, say, b 1 is a cut vertex, the component hanging off b 1 can be embedded in the face (h, b 1 , v 1 , h). But then it can easily be moved into C. Similarly, a component that is incident only to v 5 and v 6 can end up in the face (h, v 5 , v 6 , h), but again, the component can be moved inside C.)

Similarly, for a region of the second type, say r 3 , the graph G r3 is outerplanar with a special drawing where all the vertices must be on the (v 3 , v 5 )-arc of the disk subtended by the two frame edges e 3 and e 2 bounding the region r 3 . We augment r 3 similarly as r 1 ; see Fig. 5d. For the augmented graph G * r3 , we add to G r3 a boundary vertex b neighboring all vertices on the (v 3 , v 5 )-arc and a hub vertex h adjacent to v 3 , b, and v 5 . Again, G * r3 is planar since G r3 is outerplanar. Moreover, as b is adjacent to all vertices of G r3 , in every planar embedding of G * r3 , G r3 is embedded outerplanarly and, since b occurs on one side of the triangle v 3 v 5 h, the edge v 3 v 5 occurs on the boundary of this outerplanar embedding of G r3 . Thus, each planar embedding of G * r3 provides an outerplanar embedding of G r3 that fits into r 3 .

Note that each G ri fits into r i because its augmented graph G * ri is planar ( ). Moreover, as outerplanar graphs have treewidth at most two [START_REF] Mitchell | Linear algorithms to recognize outerplanar and maximal outerplanar graphs[END_REF], each graph G r is outerplanar, and adding the (up to) eight frame vertices raises the treewidth by at most 8, we see that the treewidth of G is at most 10. Namely, in order for G to have bc • (G) = 1, it must have treewidth at most 10 (and this can be checked in linear time using an algorithm of Bodlaender [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF]).

To sum up, G has a circular drawing D with at most one bundled crossing because it has treewidth at most 10 and there exist (i) β ≤ 4 frame edges e 1 , e 2 , . . . , e β (this set is denoted F ) and v 1 , . . . , v ξ frame vertices (this set is denoted V F ), (ii) a particular circular drawing D F of frame edges, (iii) the drawing of the one bundled crossing B, and (iv) γ ≤ 6 corresponding regions r 1 , . . . , r γ of the subdivided surface Ω so that the following properties hold. (Note that the frame vertices partition the boundary of the disk underlying Ω into η ≤ 8 (possibly degenerate) arcs p 1 , . . . , p η where each such p j is contained in a unique region r ij of Ω. Let V 0 (r i ) be the frame vertices incident to region r i .)

1. E(G) is partitioned into E 0 , E 1 , . . . , E γ , where E 0 ={f 1 , . . . , f β }. 2. V (G) is partitioned into V 0 , V 1 , . . . , V η , where V 0 ={w 1 , . . . , w ξ }.
3. The mapping w i ↔ v i and f i ↔ e i defines an isomorphism between the subgraph of G formed by (V 0 , E 0 ) and the graph (V F , F ).

4. For each v ∈ V 0 and each edge e incident to v, exactly one of the following conditions holds: (i) e ∈ E 0 , or (ii) e ∈ E i and v is on the boundary of r i .

5.

For each v ∈ V j , j = 0, all edges incident to v belong to E ij .

6. For each region r i , let G ri be the graph (V 0 (r i ) ∪ j : ij =i V j , E i ) (i.e., the subgraph that is to be drawn in r i ), and let G * ri be the corresponding augmented graph (i.e., as in above). Each G * ri is planar.

We now describe the algorithm that tests whether a given graph G admits a simple circular drawing with one bundled crossing. First we check that the treewidth of G is at most 10. We then enumerate drawings of up to four edges in the circle. For the drawing D F that is valid for the set F of frame edges of one bundled crossing, we define our surface and its regions (which makes the augmentation well-defined). We have intentionally phrased these properties so that it is clear that they are expressible in MSO 2 (see Section 3.4). The only property that is not obviously expressible is the planarity of G * ri . To this end, recall that planarity is characterized by two forbidden minors (i.e., K 5 and K 3,3 ) and that, for every fixed graph H, there is an MSO formula minor H so that for all graphs G, it holds that G |= minor H if and only if G contains H as a minor [START_REF] Courcelle | Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach[END_REF]Corollary 1.14]. Additionally, each G * ri can be expressed as an MSO-transduction4 of G and our variables (our transduction can be thought of as a kind of 2-copying transduction). Thus, by [START_REF] Courcelle | Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach[END_REF]Theorem 7.10] using the transduction and the MSO formula testing planarity, we can construct an MSO 2 formula ι so that when G |= ι, G * ri is planar for every i. Therefore, Properties 1-6 can be expressed as an MSO 2 formula ψ and, by Courcelle's theorem, there is a computable function f such that we can test (in O(f (ψ, t)n) time) whether G |= ψ for an input graph G of treewidth at most t. Thus, since our graph has treewidth at most 10, applying Courcelle's theorem completes our algorihtm.

Recognizing a Graph with k Bundled Crossings

We now generalize the above approach to k bundled crossings. In a drawing D of G together with a solution consisting of k bundled crossings, there are 2k bundles making (up to) 4k frame edges F . As described above, these bundled crossings provide a surface S, its subdivision Ω, and the corresponding set of regions. The key ingredient above was that every region r contained an outerplane graph G r . However, that is now non-trivial as our regions can go over and under many handles. To show this property, we first consider the following two partial drawings D A (p) and D B (p) of a matching with p + 1 edges f 0 , f 1 , . . . , f p (see Fig. 6) such that

• edge f i crosses only f i-1 mod p+1 and f i+1 mod p+1 for i = 0, . . . , p;

• the endpoints of each edge f i , i = 1, . . . , p-1, are inside the closed curve C formed by the crossing points and the edge-pieces between these crossing points;

• only one endpoint of f 0 , and only one endpoint of f p are contained in C in the drawing D A (p);

• both endpoints of f 0 and f p are contained in C in the drawing D B (p).

Note that the partial drawings D A (p) and D B (p) differ only in how the last edge is drawn with respect to the first one. Arroyo et al. [START_REF] Arroyo | Extending drawings of graphs to arrangements of pseudolines[END_REF]Theorem 1.2] showed that such partial drawings are obstructions for pseudolinearity, that is, they cannot be part of any pseudoline arrangement. Therefore, neither of these partial drawings can be completed to a simple circular drawing, that is, the

f p-1 f 0 f 1 f p f p-1 C (a) DA(p) f p-1 f 0 f 1 f p f p-1 C (b) DB(p)
Figure 6: The two types of partial drawings (for p = 6) and the closed curve C (light green) that they induce.

endpoints of the edges cannot be extended so that they lie on a circle which contains the drawing. We highlight this fact in the following lemma.

Lemma 2 ([4]

) For a matching with p + 1 edges f 0 , f 1 , . . . , f p , neither the partial drawing D A (p) nor the partial drawing D B (p) can be completed to a simple circular drawing.

Using this lemma, we can now prove the following statement.

Lemma 3 Let r be a region of the surface subdivision Ω, and let r be its projection onto the plane. Then both r and r are topological disks, that is homeomorphic to a disk (with the boundary). Moreover, the projection map is injective.

Proof: Note that the boundary of r is formed by pieces of frame edges that were lifted on the surface S as described above and by additional corner-cuts as illustrated in Fig. 5b in blue. This means that the boundary of r is a (closed) Jordan curve since we have only finitely many crossings in G. Then, we show that r does not include part of both a handle and its undertunnel, that is, the part of the surface over which the handle was built. This guarantees that the projection of r onto the plane is injective, and thus the boundary of r is a Jordan curve. We will also show that r does not include holes. Then we can conclude that r is homeomorphic to a disk using the Jordan-Schoenflies theorem, which says that for any closed Jordan curve there is a homeomorphism of the plane that maps the curve to the unit circle. Suppose now, for a contradiction, that there are bundled crossings for which r contains both the handle and its undertunnel; see Fig. 7a. Then there exists a non-intersecting Jordan arc γ ⊂ r going over and under some of these handles. Consider the orthogonal projection γ of γ on the disk of the drawing D (see Fig. 7b) and notice that it self-intersects where it went over and under some handle in r. Choose the piece γ 1 of γ separated by the self-intersection point X Q , corresponding to some bundled crossing Q, such that γ 1 starts and ends in X Q and no intersection point (except X Q ) is met twice when walking along γ 1 once; see Fig. 7b.

Let P be the planarization of the projected drawing, and let P be a copy of P without the edges that intersect γ 1 . Consider the edges of P in the interior of the closed curve γ 1 (see Fig. 7c) that can be seen from γ 1 , that is, for each γ (a) A region r with handles and undertunnels corresponding to the same bundled crossings and a curve γ that goes over and under such handles; of such edges, we can draw a curve β from some point of γ 1 so that β does not intersect γ 1 and any other edge of P . We call the edges of the drawing D that contain the edges of the planarization P seen from γ 1 the profile of γ 1 ; see Fig. 7d. These edges form a partial drawing D A (p) for some p > 0; see Fig. 6a. According to Lemma 2, however, such a partial drawing cannot be completed to a valid simple circular drawing; contradiction.

As for holes, it is easy to see that if r had a hole, the profile of any curve around this hole would yield a partial drawing D B (p) for some p > 0; see Fig. 6b. Again, according to Lemma 2, such a partial drawing cannot be completed to a valid simple circular drawing; contradiction.

Note that, since r is a topological disk, its lifting r is also a topological disk.

In particular, since our projection is injective, a drawing on r can be regarded as a drawing on r and vice versa.

The next lemma concerning treewidth is a direct consequence of Lemma 3.

Lemma 4 If a graph G admits a circular layout with k bundled crossings then its treewidth is at most 8k + 2.

Proof: If the graph G can be drawn in a circular layout with k bundled crossings then there exist at most 4k frame edges. According to Lemma 3, the merates all possible simple drawings of at most 4k edges in the circle 5 . For each drawing, it further enumerates the possible ways to form at most k bundled crossings so that every edge is a frame edge of at least one bundled crossing. Then, for each such bundled drawing D F , we build an MSO 2 formula ϕ (see Section 3.4) to express Properties 1-6. Finally, since G has treewidth at most 8k + 2, we can apply Courcelle's theorem on (G, ϕ).

MSO 2 : Definitions and Our Formula for a Specific Layout of the Frame Edges

This subsection serves two purposes. First, we define the class MSO 2 of logical formulas as needed for our application of Courcelle's theorem; see Theorem 5.

Second, we describe how to express the needed condition of our algorithm (as given by Properties 1-6) in this logic.

Defining MSO 2 . The class of formulas expressible in MSO 2 is defined as follows; see also the textbook of Courcelle and Engelfriet [START_REF] Courcelle | Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach[END_REF] for more background.

Extended Monadic Second-Order Logic (MSO 2 ) is a subset of second-order logic that can be used to express certain graph properties. It is built from the following primitives:

• variables for vertices, edges, sets of vertices, and sets of edges;

• binary relations for: equality (=), membership in a set (∈), subset of a set (⊆), and edge-vertex incidence (I);

• standard propositional logic operators: ¬, ∧, ∨, →, and ↔;

• standard quantifiers (∀, ∃) which can be applied to all types of variables.

Note that, if we drop the " 2 " then we have Monadic Second-Order Logic (MSO) where the only difference is that we are now not allowed to quantify over edge sets. Additionally, the convention for MSO formulas is to use a binary adjacency function (adj G ) instead of the incidence function as in the definition of MSO 2 above.

For a graph G and an MSO 2 (or MSO) formula ψ, we use G |= ψ to indicate that ψ can be satisfied by G in the obvious way. Note that we will use an additional tool in the construction of our formula below, namely, that of MSOtransductions. Essentially, an L-transduction is just the name for the operation of constructing the model of one graph/structure from the model of another graph/structure in the language of the logic L. A rigorous treatment on transductions is given in the book of Courcelle and Engelfriet [11, Section 1.7.1, and Definitions 7.6 and 7.25]. For example, an MSO-transduction that constructs a graph G (modelled for MSO, using a vertex set V (G ) and adjacency function adj G ) by adding a universal vertex x to a given graph G (modelled for MSO 2 , using a vertex set V (G), edge set E(G), and incidence function I G ) can be written as follows:

V (G ) := {x} ∪ V (G) adj G (u, v) := (u = v) ∧ (∃e ∈ E(G)) (I G (e, v) ∧ I G (e, u)) ∨ (x = u) ∨ (x = v) .
We will describe our augmented graphs (from Property 6) as an MSOtransduction (also whose target is modelled for MSO and whose original graph is modelled for MSO 2 ) and this will allow us (via [START_REF] Courcelle | Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach[END_REF]Theorem 7.10]) to have an MSO 2 formula to implicitly check the planarity of our augmented graphs inline within our (main) MSO 2 formula (where our formula is applied only to the graph prior to augmentation).

The formula for D F . We now construct an MSO 2 formula to express the following problem:

• Given a graph G = (V, E) and a simple circular drawing D F with k bundled crossings so that F = {e 1 , . . . , e β } is the set of frame edges (and D F has no other edges) and V F = {v 1 , . . . , v ξ } is the set of frame vertices (and D F has no other vertices);

• determine whether G has a simple circular drawing with k bundled crossings so that the frame edges and vertices occur as in D F . This is based on Properties 1-6 on page 11: we express them as MSO 2 formulas. Properties 1 and 2 simply state that a set of elements is partitioned into a certain number of disjoint subsets. We use a formula stated by Bannister and Eppstein [START_REF] Bannister | Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth[END_REF] to express this in MSO 2 . For example, partitioning of a set E into disjoint subsets E 0 , E 1 , . . . , E γ can be done as follows:

Partition(E; E 0 , . . . , E γ ) = (∀e ∈ E) γ i=0 e ∈ E i ∧ i =j ¬(e ∈ E i ∧ e ∈ E j ) .
We will additionally use the following formula to state that a vertex set V is the set of endpoints of an edge set E :

Incident(V , E ) = (∀e ∈ E ) (∀v ∈ V (G)) [I(e, v) ⇔ v ∈ V ].
We now turn to the properties more specific to our fixed drawing D F with β ≤ 4k frame edges F = {e 1 , e 2 , . . . , e β } whose endpoints form the set V (F ) = {v 1 , v 2 , . . . , v ξ }, where ξ ≤ 2β. As discussed in Section 3.1 and Lemma 3, this drawing induces a corresponding set of regions r 1 , . . . , r γ . Property 3 ensures that certain edges E 0 = {f 1 , f 2 , . . . , f β } and their endpoints V 0 = {w 1 , w 2 , . . . , w ξ } of the graph G induce a graph isomorphic to (V (F ), F ). This can be modeled by the following formula.

θ 3 (V 0 , E 0 ) = ∀i, j ∈ {1, 2, . . . , ξ} (∃f ∈ E 0 ) I(e, w i ) ∧ I(f, w j ) ⇔ (∃e ∈ F ) I(e, v i ) ∧ I(e, v j )
To express Properties 4 about the adjacencies of the frame vertices, we introduce the following piece of notation. For each vertex v i ∈ V (F ) with i ∈ {1, 2, . . . , ξ}, we denote by σ(i) the set of indices of the regions incident to v i in the drawing D F . For example, in the case of one bundled crossing (see Fig. 5), σ(1) = {1, 6}. Then Property 4 can be expressed in MSO 2 as follows:

θ 4 (V 0 , E 0 ) = ∀i ∈ {1, 2, . . . , ξ} (∀e ∈ E) I(e, w i ) ⇒ e ∈ E 0 ∨ (∃j ∈ σ(i)) [e ∈ E j ] .
Property 5 expresses that, for each non-frame vertex v ∈ V j , all edges incident to v are contained in E ij (recall that i j is the index of the region containing the set V j of non-frame vertices and that E ij is the set of non-frame edges of this region):

θ 5 (V 1 , . . . , V η ) = ∀j ∈ {1, 2, . . . , η} ∀v ∈ V j ∀e ∈ E I(e, v) ⇒ e ∈ E ij
Finally, we turn to Property 6. First, note that testing planarity of a graph G can be expressed as follows where the formula for Minor H (G) does not need edge set quantification (i.e., it is in MSO) [START_REF] Courcelle | Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach[END_REF]Corollaries 1.14 and 1.15]:

Planar(G) = ¬Minor K5 (G) ∧ ¬Minor K3,3 (G).
Now, we describe the MSO-transduction6 τ i of G to G * ri (for each region r i ; see Section 3.3) subject to the variables w 1 , . . . , w ξ , V 1 , . . . , V η , f 1 , . . . , f β , E 1 , . . . , E γ . Note that in our transduction, the input uses the format allowing for edge set quantification (i.e., where we have the objects V ∪ E and the binary incidence function I), but our output involves the format without edge set quantifications (i.e., where we have the objects V and the binary adjacency function adj). Let j 1 , . . . , j ζ be the indices of the frame vertices incident to region r i and suppose these are ordered cyclically as in D F . Further, let V l1 , . . . , V lα be the sets corresponding to the arcs of the boundary of r i (in order). With this notation, we can now set up the transduction τ i which describes our graph G * ri in terms of our variables (note that in the statement of [START_REF] Courcelle | Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach[END_REF]Theorem 7.10] our variables are the parameters). Note that the symbols h, b 1 , b 2 , . . . , b α are new objects that are added in the construction (namely, the hub and boundary vertices of G * ri ). Further, let C be the cycle of the wheel, that is,

V (C) = {v j1 , . . . , v j ζ , b 1 , . . . , b α }.
For each vertex x ∈ V (C), let N C (x) be the set consisting of the two neighbors of x in C. Now we can describe the transduction τ i as follows.

V (G * ri ) := {h} ∪ V (C) ∪ α j=1 V lj adj G * r i (u, v) :=(u = v) ∧ (∃e ∈ E i ) (I(e, v) ∧ I(e, u)) ∨ (h = u) ∧ (v ∈ V (C)) ∨ (h = v) ∧ (u ∈ V (C)) ∨   α j=1 u = b j ∧ v ∈ V lj   ∨   α j=1 v = b j ∧ u ∈ V lj   ∨ (u ∈ V (C)) ∧ (v ∈ N C (u)) ∨ (v ∈ V (C)) ∧ (u ∈ N C (v)) .
With this transduction τ i and the expression Planar(G), we can now apply [START_REF] Courcelle | Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach[END_REF]Theorem 7.10] to obtain the MSO 2 formula ι i which, when applied to G (together with our variables), allows us to express that G * ri is planar. Namely, by taking the conjunction of all of these ι i , we obtain the needed MSO 2 formula ι (which can be applied to G and our variables) to express that all of the G * ri 's are planar. Now we construct the MSO 2 formula corresponding to Properties 1-6. The formula depends on the drawing D F of the set of frame edges F .

realizable D F (G) ≡ (∃f 1 , . . . , f β , E 0 , E 1 , . . . , E γ , w 1 , w 2 , . . . , w ξ , V 0 , V 1 , . . . , V η ) E 0 = {f 1 , . . . , f β } ∧ V 0 = {w 1 , w 2 , . . . , w ξ } ∧ Partition(E; E 0 , E 1 , . . . , E γ ) ∧ Partition(V ; V 0 , V 1 , . . . , V η ) ∧ Incident(V 0 , E 0 ) ∧ θ 3 (V 0 , E 0 ) ∧ θ 4 (V 0 , E 0 ) ∧ θ 5 (V 1 , . . . , V η ) ∧ ι(f 1 , . . . , f β , E 1 , . . . , E γ , w 1 , w 2 , . . . , w ξ , V 1 , . . . , V η ) .

Bundling a Drawing

We now establish the following parameterized results for bundling a given drawing.

Theorem 6 Let G be a graph with n vertices and m ≥ n edges, and let D be a drawing of G. (c) If D is simple and circular, testing whether bc

• (G, D) ≤ k is FPT in k; it takes 2 O( √ k log k) + O(m) time. (d) For a permutation π of V (G), testing whether bc • (G, π) ≤ k is FPT in k; it takes 2 O(k 2 ) + O(m) time.
To prove this theorem, we will examine the number of combinatorially different bundled crossings we can make in our given fixed drawing D. Namely, let B(D) be the entire family of subsets of crossings in D such that each subset corresponds to a bundled crossing in D, that is, for each bundled crossing, the subset S of the crossings in D contained in it is an element of B(D). We show that |B(D)| ∈ O(c 4 ) where c is the number of crossings in D; see Lemma 6. For the case when D is simple, we show that |B(D)| ∈ O(m 4 ) where m is the number of edges in D; see Lemma 5. Note that each element of B(D) forms a connected subgraph in the planarization of the drawing. So, by finding k such connected subgraphs that are pairwise disjoint and together cover the crossings of D, we can bundle the drawing to have at most k crossings. Marx and Pilipczuk [START_REF] Marx | Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams[END_REF] studied exactly this type of disjoint covering problem. Their result is as follows.

Theorem 7 ([25, Theorem 1.3]) Let G be a planar graph, let B be a family of connected vertex sets in G, let C ⊆ V (G) be a set of vertices, and let k be an integer. In time 1) , we can find a set S of at most k pairwise disjoint objects in B that maximizes the number of vertices of C in the union of the vertex sets in S.

|B| O( √ k) n O(
We use Theorem 7 and an algorithm of Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] to prove Theorem 6. (c) Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] showed that testing bc • (G, π) ≤ k can be kernelized down to an instance with at most 16k edges (or report that (G, π) is a no-instance) in O(m) time. This also applies to a given simple circular drawing. Thus, by applying their kernelization and using (b) with m ≤ 16k, we establish (c).

Proof of

(d) Here, we use (b) to improve the FPT algorithm of Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] for determining whether bc • (G, π) ≤ k. (Their algorithm runs in time k O(k 2 ) + O(m) and proceeds in three stages). First, it applies a kernelization step to obtain a graph with at most 16k edges in O(m) time; second, it enumerates all possible O 2 0.657k 2 weak pseudoline arrangements of 16k pseudolines [START_REF] Felsner | On the number of arrangements of pseudolines[END_REF]; and third, for each such weak pseudoline arrangement it partitions the crossings into the minimum number of bundled crossings by exhaustive search in time O k 128k 2 . For this last step, we apply (b) instead (now with m ≤ 16k), leading to (16k

) O( √ k) = 2 O( √ k log k) time, and 2 O(k 2 ) + O(m) time in total.
Note that since the number of crossings in a non-simple drawing is not bounded by a function of the number of edges m in the drawing, we do not obtain an analogous result for the circular layout as in Theorem 6(c) by using the kernelization technique of Alam et al. [START_REF] Alam | The bundled crossing number[END_REF]. On the other hand, we present a 2 O(m) -time algorithm for not necessarily simple drawings in circular layouts in the context of storyline visualization; see Section 5.

We now discuss the size of the family B(D) for some drawing D. Note that each bundled crossing in D involves two pairs of frame arcs, and, conversely, two pairs of frame arcs can determine at most one bundled crossing. We show that if D is simple, then this is also true for frame edges, that is, two pairs of frame edges can determine at most one bundled crossing; see Lemma 5. This allows us to bound the number of distinct bundled crossings by the number of edges from above, and thus, the size of the family B(D). Proof: Consider two bundles that form a given bundled crossing. Each bundle has at most two not necessarily distinct frame edges. For the reverse direction, consider a bundled crossing B and let (e 2 , e 4 ), (e 1 , e 3 ) be the two pairs of frame edges each corresponding to a bundle. Let c ij , for i = 1, 3, j = 2, 4 be the frame crossing of e i and e j (if it exists). There are three cases how these two pairs can determine a bundled crossing: (a) e 1 = e 3 and e 2 = e 4 : then B is a single crossing, clearly there cannot be another bundled crossing determined by the same pairs; (b) e 1 = e 3 and e 2 = e 4 (the case where e 1 = e 3 and e 2 = e 4 is symmetric): then B consists of all crossings on e 1 between c 12 and c 14 , since e 1 and e 2 can cross e 1 at most once, there cannot be another bundled crossing; or (c) the edges are pairwise different, then all the crossings c ij exist and are distinct and any other bundled crossing would imply that for some fixed i and j the crossings c ij occurred twice, which is impossible in a simple drawing.

In the case of a not necessarily simple drawing D, the number c of crossings cannot be bounded in terms of the number m of edges. But if we define the size of an instance in terms of the number of crossings, it is easy to see that B(D) is of size polynomial in c. Proof: Every bundled crossing can be determined by two pairs of frame arcs. Since each crossing can be incident to at most four arcs, four crossings can determine at most 4 4 different bundled crossings. Therefore, the total number of bundled crossings is polynomially bounded by the number of crossings, namely |B(D)| ≤ 16c 4 .

Bundling Storyline Visualisations Is FPT

For our purposes, a storyline drawing D is a set of m x-monotone curves. Such curves cannot self-intersect, but a pair of curves is allowed to intersect each other multiple times; we only forbid the existence of digonal faces, that is, two curves intersecting each other twice in a row. Finally, we assume here that all curves start on distinct points of a vertical line v left and end on distinct points of a vertical line v right . This is common in storyline visualizations, but this restriction can be dropped with additional care. We prove the following.

Theorem 8 Given a storyline drawing D with m characters and c crossings, bc s (D) can be computed in O(ϕ 2m mc) ⊂ O(2.62 m mc) time, where ϕ is the golden ratio. This runtime is fixed parameter tractable in m. An optimal bundling can be constructed in the same time.

Recall that I(D) is the set of crossings. Each curve, being x-monotone, gives a left-to-right order of its incident crossings. These orders give a partial order on I(D). Let π be an arbitrary linear extension of these partial orders, which can be found in polynomial time given D. Then we subdivide D into columns according to π: see Definition 2 and Fig. 10. We call a face of this subdivision a cell. In this section we define a way to label the cells to describe any bundling of the drawing. The algorithm for Theorem 8 is based on dynamic programming over such labelings.

Definition 2 A subdivision S(D) consists of the drawing D together with: horizontal lines h top and h bot above and below all curves; vertical lines v left and v right going through the left and right endpoints of the curves, respectively; and a set of c y-monotone curves with the following properties:

• for each crossing X in I(D), there is a unique curve going through X,

• each curve crosses h top , h bot and all curves of D, • the curves do not intersect each other, and they are totally ordered from left to right according to π.

See Fig. 10a for an example of a drawing D with its subdivision S(D). Let C be the set of bounded faces of S(D); we call the elements of C the cells in order to distinguish them from the faces of D. A drawing of S(D) in Fig. 10b helps to understand its structure. (This drawing is stretched similarly to a For cells not inside a bundled crossing, there are five options.

• • • S • • • S • • • • • • • • • • • • • • • • × × × × ↑ ↑ ↑ ↑ ↓ ↓ ↓ ↓ 1
S This cell is directly left of the π-earliest crossing of a bundled crossing: it "starts" a bundled crossing.

• This cell does not touch the boundary of a bundled crossing, except possibly in a point.

↓ Only the lower boundary of this cell bounds a bundled crossing.

↑ Only the upper boundary of this cell bounds a bundled crossing.

Both the upper and lower boundary of this cell bound a bundled crossing

We call a function from the set C of cells to the set L of labels a labeling. A labeling is called real if there exists a bundling of D where each cell satisfies the condition of its label. We now observe four necessary properties of real labelings. Afterward, we prove that they are sufficient.

Crossing Property Any crossing must be part of a bundled crossing (though possibly a degenerate one). Consider the six cells surrounding a crossing in S(D). If the crossing lies in the interior of a bundled crossing, all six cells are labeled × in the real labeling. Otherwise it lies on the boundary of a bundled crossing. Enumeration reveals the finite set of ways to label these cells that can possibly be real: see Fig. 11. Any other way to label the six cells around the crossing directly contradicts the conditions for the labels.

Column Property Note that in a real labeling, a column of S(D) can have at most one cell labeled 'S', since by construction only one cell per column is left of a crossing. Now consider the sequence of labels encountered top to bottom in a column, for example [•, •, ↓, ×, ↑, •] in the third column of Fig. 10b. For any real labeling, this sequence describes being inside (×) and outside (•) of bundled crossings, with ↓, ↑ and marking the transitions, and possibly the label 'S' in place of • in one particular cell (left of the crossing). Such sequences without 'S' are walks through the directed graph in Fig. 12; the Column property says that precisely these sequences are allowed, with the addition of also allowing 'S' in the appropriate cell (and only there).

Row Property In any real labeling, horizontally adjacent cells have the same label unless they share a crossing on their boundary (and in that case the change is governed by the Crossing property), where • and 'S' are considered the same: the labels • and 'S' both describe a cell that does not touch the boundary of a bundled crossing. Such pairs of horizontally adjacent cells must have the same label, because they have the same incidences to any bundled crossings: these incidences can only change at crossings. Consider for example the sequence of labels encountered left to right in the third row for Fig. 10b: [•,↓,↓,↓,↓,•]. For the Row property, the third and fourth labels must be the same; the other pairs are exempt due to sharing a crossing. The 'S' in the second row is allowed to the right of • since the two labels are considered equal for the Row property.

Quadrangle Property In any real labeling, all faces inside a bundled crossing are quadrangles. Therefore, only cells contained in a quadrangular face of D can have the label ×.

These properties are necessary for real labelings (as argued above) and, once we fix the leftmost and rightmost columns of the labeling, they are also sufficient.

Lemma 7 A labeling C → L is real if and only if:

1. the first column contains 'S' left of its crossing and • everywhere else, 2. the last column contains • everywhere, and 3. the Crossing, Column, Row, and Quadrangle properties hold everywhere.

The number of bundled crossings in the corresponding bundling equals the number of cells with label 'S'.

Proof: First observe that in any real labeling, the first column consists of all • except the label 'S' in the unique cell adjacent to a crossing: none of the cells bound (or are in) a bundled crossing except that the 'S' cell necessarily touches one in a point. Similarly in any real labeling the last column cannot have cells that are contained in a bundled crossing or adjacent to a crossing on their right, so they are all labeled •. As argued above, the Crossing, Column, Row, and Quadrangle properties hold everywhere in any real labelling. This establishes one direction of the lemma. We now show that if a labelling satisfies the three conditions of the lemma, then it is real. Consider a connected component of cells labeled ×. Based on the Row and Crossing properties, the surrounding cells are correctly labeled with arrows and an 'S' label. Call such a connected component a blob. We show that each blob is indeed a bundled crossing by Definition 1. (Note that blobs are nondegenerate bundled crossings; we handle degenerate bundled crossings later.)

Let B be a blob. Call crossing on the boundary of B a convex corner if no curve in this crossing goes into the interior of the blob; a side if one curve goes into the interior, or; a reflex corner if two curves go into the interior. Notice that the "start", "top corner", "bottom corner", and "end" configurations of the Crossing property represent convex corners, and the other configurations with × represent sides. Therefore, a blob cannot have reflex corners. Thus, a blob is a topological disk. Moreover, the first column of S(D) contains no × labels, so a blob has a unique "start" configuration. Now we trace the boundary of B, starting at its π-earliest crossing X, and we will find the four frame arcs. Start from X and follow the boundary along one of the curves and call this frame arc e 1 . We switch to the next frame arc whenever we encounter a convex corner. This process is repeated until we get back to X, which must happen because the blob is a topological disk and bounded on the right by the last column (which does not contain any ×). Let e 1 , e 2 , . . . , e k be the frame arcs encountered. We only switched from a frame arc to the next at convex corners, and according to the Quadrangle property all faces in the blob are quadrangles. Then k = 4, since that is the only way to close a loop around quadrangles using only convex corners. In fact, since all faces in the blob are quadrangles, the crossings inside B form a grid and therefore B is a bundled crossing.

Consider a cell labeled 'S' that does not precede a blob. If the "single crossing" configuration of the Crossing property applies, this correctly describes a singleton bundled crossing. Otherwise, a "start linear up" or "start linear down" configuration must apply (Crossing property). Because of the "continue linear" configurations and the Row property, this must propagate and can only end in an "end linear up" or "end linear down" configuration. This correctly describes a linear bundled crossing. Therefore, a labeling that starts correctly in the first column, where the properties hold everywhere, and that arrives correctly in the final column, is real.

In preparation for the runtime bound of Theorem 8, we now bound the number of ways to label a column that are consistent with the Column property.

Lemma 8

The number of length-n strings over L that are consistent with the Column property is O(ϕ 2n ) ⊂ O(2.62 n ), where ϕ is the golden ratio. The strings can be enumerated with linear-time overhead.

Proof: Enumerating the walks in the graph from Fig. 12, with the additional option of having 'S' in place of • in one particular cell, can be achieved in depth-first fashion using a stack. The optional 'S' at most doubles the number of accepted strings, so we ignore it for the asymptotic analysis and consider only the walks in the graph. We also ignore that there are two starting nodes (• and ↓), since again this only involves a factor two. Now consider the adjacency matrix A of the graph; here the nodes are given in the order •, ↓, ↑, ×, .

A =      
1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 1

     
The characteristic polynomial det(A -λI) of the matrix A is -λ 5 + 3λ 4 -λ 3 . Its roots are 0 of multiplicity three, 1 2 (3 + √ 5) = ϕ 2 , and ϕ -2 , where ϕ is the golden ratio. Since the root with the largest absolute value is ϕ 2 > 1 and it has multiplicity one, the number of walks of length n is O(ϕ 2n ). The lemma follows. (See, for example, Ardila's treatment [START_REF] Ardila | Algebraic and geometric methods in enumerative combinatorics[END_REF] of algebraic methods for counting walks.)

Proof of Theorem 8: We use dynamic programming, moving from left to right by column of S(D): with L ∈ L m+1 and i a column, let f (L, i) be the minimum number of 'S' labels in any labeling of the columns up to column i, ending with the labels L for column i. By Lemma 8, there are only O(ϕ 2m ) values of L that satisfy the Column property and they can be enumerated with linear overhead. Each individual f (L, i) can be computed with a constant number of lookups of f ( • , i -1): by the Row property only the three rows adjacent to the crossing between the columns can change and the Crossing property gives a finite set of options for how they can change.

graph G and a vertex order π. It seems plausible to reduce from SortingBy-Transpositions, but it is difficult to keep the resulting drawings simple.

We remind the reader of the open problem posed by Alam et al. [START_REF] Alam | The bundled crossing number[END_REF] and Fink et al. [START_REF] Fink | Bundled crossings in embedded graphs[END_REF] concerning the computational complexity of bc • (G).

  ẽ3

Figure 1 :

 1 Figure 1: (a) A non-degenerate bundled crossing B and (b) a degenerate bundled crossing B ; crossings belonging to a bundled crossing are marked with crosses

  and Philipczuk [25, Theorem 1.3] (see page 21) to test whether bc(G, D) ≤ k in m O( √ k) time for any simple drawing D with m edges. This yields an FPT-algorithm for testing whether bc • (G, D) ≤ k in 2 O( √ k log k) +O(m) time and for testing whether bc •

Figure 3 :

 3 Figure 3: A single bundled crossing outside the fundamental polygon [2, Fig. 3]

Figure 4 :

 4 Figure 4: Obtaining a circular drawing with k bundled crossings of G from the embedding of G on a surface of genus k.

Figure 5 :

 5 Figure 5: (a) Bundled crossing; (b) regions, corner-cuts in blue; (c),(d) the augmented graphs G * r1 and G * r3 consist of the edges of G r1 and G r3 (in the blue regions) as well as augmentation vertices and edges (drawn in black)

X Q γ 1 γ

 1 (b) projection of the region r and projection γ of the curve γ on the drawing D in the plane. The curve γ 1 (light red) is a part of γ that starts and ends in XQ. the profile of the curve γ 1 (light blue). These edges form a partial drawing DA(p).

Figure 7 :

 7 Figure 7: Illustration to the proof of Lemma 3.

  (a) If D has c crossings, we can test whether bc (G, D) ≤ k in c O( √ k) + O(m + c) time. (b) If D is simple, we can test whether bc(G, D) ≤ k in m O( √ k) + O(m) time.

  Theorem 6: (a) Consider a drawing D of G with c crossings, and let B = B(D). By Lemma 6, |B| ∈ O(c 4 ). Let D be the plane graph obtained from D by creating a vertex at each crossing point in D (note that D does not contain the vertices of G), and connecting two such vertices if they are consecutive along an edge in D. Clearly, each element in B forms a connected subgraph of D . Thus, applying Theorem 7 with G = D , B = B(D), C = V (D ) establishes (a). (b) This follows as in (a). Namely, since D is simple, by Lemma 5, |B| ∈ O(m 4 ). This establishes (b).

Lemma 5

 5 Let D be a simple drawing D with m edges. Each bundled crossing determines at most two pairs of frame edges, and, conversely, two pairs of frame edges can determine at most one bundled crossing. In particular, |B(D)| ≤ m 4 .

Lemma 6

 6 For any not necessarily simple drawing D with c crossings |B(D)| ∈ O(c 4 ).

Figure 10 :

 10 Figure 10: Bundling of a storyline drawing: curves added in S(D) are dashed and a bundling of the crossings is indicated in gray. Note the degenerate bundled crossing at crossing 2.

2 Figure 11 :Figure 12 :

 21112 Figure 11: All possible configurations of labels around a crossing on the boundary of a bundled crossing, where the Greek variables may be substituted as follows: α ∈ {•, ↑}, β ∈ {•, ↓}, γ 1 γ 2 ∈ {• ↓, ↑ }, δ 1 δ 2 ∈ {• ↑, ↓ }.Multiple occurrences of the same variable within one configuration must be substituted consistently, so for example the two α in the top left configuration must both be • or both be ↑. (If the crossing is in the interior of a boundled crossing, all six cells must be ×.)

Fink et al. [16] used "embedding" and bc(E) where we use "drawing" and bc(G, D), respectively.

I.e., computing the fewest handles to attach to the sphere so that G can be drawn on the resulting surface without any crossings.

This augmentation may sound overly complicated, but is written as to easily generalize to more bundled crossings.

For the formalities of transductions, see the book of Courcelle and Engelfriet [11, Section 1.7.1, and Definitions 7.6 and 7.25].

i.e., at most 4k curves extending to infinity in both directions where each pair of curves cross at most once. The number of such drawings is proportional to k, and efficient enumeration has been done for the case when every pair of curves cross exactly once[START_REF] Felsner | On the number of arrangements of pseudolines[END_REF].

Recall that, a transduction is essentially just the name for the operation of constructing the model of one graph/structure from the model of another graph/structure in the language of MSO.

Acknowledgements. We thank Bruno Courcelle for clarifying discussions on the tools available when working with his meta-theorem and in particular MSO 2 . We thank the reviewers for their helpful comments, in particular for pointing out a gap in the correctness proof of our algorithm for bundling storylines, which we fixed subsequently.

JGAA, 0(0) 0-0 (0) 31

support by the joint DFG-GA ČR grant WO 758/11-1; M.K. and A.R. acknowledge support by the joint DFG-SFFRU grant WO 758/9-1.

Figure 8: (a) A bundled drawing D with six bundled crossings (pink); parallel (blue) edges can be inserted to avoid degenerate bundled crossings; (b) the corresponding surface of genus 6; the components of the surface that are not regions are marked in green; the region r (light blue) has a boundary consisting of the arcs of the disk (red) and the arcs c 1 , c 2 , c 3 , and c 4 (traced in orange). removal of their endpoints breaks up the graph into outerplanar components. The treewidth of an outerplanar graph is at most two [START_REF] Mitchell | Linear algorithms to recognize outerplanar and maximal outerplanar graphs[END_REF]. Moreover, adding a vertex to a graph raises its treewidth by at most one. Thus, since deleting at most 8k frame vertices leaves behind an outerplanar graph, G has treewidth at most 8k + 2.

We now prove Theorem 2, which says that deciding whether bc

Proof of Theorem 2: We use Lemma 3 and extend the algorithm of Section 3.2.

Suppose that G has a circular drawing D with at most k bundled crossings. Then D contains a set F of (up to) 4k frame edges of these bundled crossings. As discussed before, F together with D defines a subdivided topological surface Ω containing a set R of regions. As in the case of one bundled crossing, each edge of G not in F is contained in exactly one such region, and each vertex of G either is incident to an edge in F (in which case it belongs to at least two regions) or belongs to exactly one region.

Throughout the proof we refer the reader to Fig. 8 for an example. By Lemma 3, each region r in R is a topological disk. Therefore, the graph G r whose vertices lie on the boundary of r and whose edges lie in the interior of r is outerplane with respect to the given order of the vertices along the boundary. This boundary consists, in clockwise order, of arcs p 1 , . . . , p α of the outer boundary of S (marked in red in Fig. 8b) and Jordan arcs c 1 , . . . , c α (traced in orange in Fig. 8b), each of which connects two consecutive arcs of S. For i ∈ {1, . . . , α}, let u i and u i be the endpoints of p i , in clockwise order. The arc p i can degenerate to a single point; then u i = u i ; see Fig. 9. So u i and u i+1 (where u α+1 is u 1 ) are the endpoints of c i . No vertex of G r lies in the interior of c i .

We now describe G * r . First, we add a hub vertex h. Then, for each i ∈ {1, . . . , α}, if u i and u i+1 (where u α+1 is u 1 ) are not adjacent, we add an edge between them. If the arc p i is non-degenerate, we add a boundary vertex b i adjacent to all vertices on p i (including u i and u i ) and make h adjacent to u i , b i , and u i . Otherwise, we make h adjacent to u i = u i and identify b i with u i and u i . The reason for this identification is technical; it allows us to iterate over all (degenerate or non-degenerate) arcs and address their boundary vertices; see Section 3.4 (page 20).

Observe that the resulting graph G * r is planar due to the special outerplanar drawing of G r in r. Moreover, in every planar embedding of G * r , there is an outerplanar embedding of G r where the cyclic order of the arcs c i and the sets of vertices mapped to the p i 's match their cyclic order in r, implying that G r fits into r. This is due to the fact that the simple cycle C around h must be embedded planarly, with all of G r inside (with the possible and easy-to-fix exceptions described in Section 3.2 concerning the cycle C there). Then the order of the vertices in an outerplanar embedding of G r is the order of the vertices incident to b 1 , . . . , b α in a planar embedding of G * r . So the planarity of G * r guarantees that G r fits into r as needed.

The reason why G has a circular drawing D with at most k bundled crossings is that there is a β-edge k-bundled crossing drawing D F (of the graph formed by F ), whose corresponding surface S consists of regions r 1 , . . . , r γ (note: γ ≤ 2β ≤ 8k) so that Properties 1-6 hold.

Our algorithm first checks that the treewidth of G is at most 8k + 2. Recall that this can be done in linear time (FPT in k) [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF]. The algorithm then enu-Algorithm 1: Dynamic program for computing the bundled crossing number of storyline visualizations.

Input: Drawing D.

Output: Bundled crossing number bc s (D).

A single column c of S(D).

Output:

Enumerates all ways to label the column according to the Column property.

Subroutine: Enum-Valid-Predecessors(c pred , c curr , L) Input:

Adjacent columns c pred and c curr of S(D), labeling L for c curr .

Output:

Enumerates all ways to label c pred according to the four properties, given that c curr is labeled L.

See Algorithm 1 for pseudocode, where F (L, i) is used to store and look up values of f (L, i); we use the convention that accessing F (L, i) returns ∞ if that value has not been stored yet. The values can be accessed in O(m) time by storing them in a prefix tree (indexed by L) per column. This leads to a total runtime of O(ϕ 2m mc).

If desired, the bundling itself can be read from F . In that case, the algorithm uses O(ϕ 2m mc) space: the c prefix trees each store O(ϕ 2m ) items and have height m + 1. If only the bundled crossing number is required, space usage can be improved to O(ϕ 2m m) by storing only two columns at a time.

Open Problems

Given our new FPT algorithm for simple circular layouts, it would be interesting to improve its runtime and to investigate whether a similar result can be obtained for general simple layouts. A starting point could be the FPT algorithm of Kawarabayashi et al. [START_REF] Kawarabayashi | Computing crossing number in linear time[END_REF] for computing the usual crossing number of a graph. We also conjecture that it is NP-hard to compute bc • (G, π), given a