Otfried Cheong
email: otfried@kaist.ac.kr.

Xavier Goaoc
email: goaoc@loria.fr.

Andreas Holmsen
email: andreash@mi.uib.no

Sylvain Petitjean
email: petitjea@loria.fr.

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

We prove Helly-type theorems for line transversals to disjoint unit balls in R d . In particular, we show that a family of n 2d disjoint unit balls in R d has a line transversal if, for some ordering ≺ of the balls, every subfamily of 2d balls admits a line transversal consistent with ≺. We also prove that a family of n 4d -1 disjoint unit balls in R d admits a line transversal if every subfamily of size 4d -1 admits a transversal.

Helly's celebrated theorem, published in 1923, states that a finite family of convex sets in R d has non-empty intersection if and only if every subfamily of size at most d + 1 has non-empty intersection. Subsequent results of similar flavor (that is, if every subset of size k of a set S has property P then S has property P) have been called Helly-type theorems and the minimal such k is known as the associated Helly number. Helly-type theorems and tight bounds on Helly numbers have been the object of active research in combinatorial geometry. In this paper, we investigate Helly-type theorems for the existence of line transversals to a family of objects, i.e. lines that intersect every member of the family.

History. The earliest Helly-type theorems in geometric transversal theory appeared about five decades ago. In 1957, Hadwiger [START_REF] Hadwiger | Über Eibereiche mit gemeinsamer Treffgeraden[END_REF] showed that an ordered family S of compact convex figures in the plane admits a line transversal if every triple admits a line transversal compatible with the ordering. (Note that a line transversal to S may not respect the ordering on S; to prove the existence of a line transversal that respects the ordering on S one needs the assumption that any four admits an order-respecting line transversal.) In what follows, we shall talk about a Hadwiger-type theorem when the family of objects under consideration is ordered.

The same year, L. Danzer [START_REF] Danzer | Über ein Problem aus der kombinatorischen Geometrie[END_REF] proved the following result concerning families of pairwise disjoint unit discs in the plane: if such a family consists of at least 5 discs, and if any 5 of these discs are met by some line, then there exists a line meeting all the discs of the family. This answered a question of Hadwiger [START_REF] Hadwiger | Ungelöste Probleme[END_REF], who gave an example (5 circles, almost touching and with centers forming a regular pentagon) which shows that 5 cannot be replaced by 4. Grünbaum [START_REF] Grünbaum | On common transversals[END_REF] showed that the same result holds if "unit disc" is replaced by "unit square", and conjectured that the result holds for families of disjoint translates of any compact convex set in the plane. This long-standing conjecture was finally proved by Tverberg [START_REF] Tverberg | Proof of Grünbaum's conjecture on common transversals for translates[END_REF]. A weaker form of the conjecture which assumed 128 instead of 5 had been established earlier by Katchalski [START_REF] Katchalski | A conjecture of Grünbaum on common transversals[END_REF].

In three dimensions, neither Hadwiger nor Hellytype theorems exist for line transversals to general convex objects, not even for translates of a convex compact set [START_REF] Holmsen | No Helly theorem for stabbing translates by lines in R d[END_REF]. However, Hadwiger [START_REF] Hadwiger | Wiskundige Opgaven[END_REF] proved a Helly-type theorem for line transversals to "thinly distributed" disjoint balls in dimension d with Helly number d 2 . A family of balls is thinly distributed if the distance between any two balls is at least the sum of their radii. Grünbaum [START_REF] Grünbaum | Common transversals for families of sets[END_REF] improved this Helly number to 2d -1 using the topological Helly theorem. For the special case of unit balls in three dimensions-but without any additional assumption on their distribution-Holmsen et al. [START_REF] Holmsen | A Hellytype theorem for line transversals to disjoint unit balls[END_REF] showed a Hadwiger-type theorem with constant 12, and a Hellytype theorem with constant 46. These constants were later improved to 9 and 18 by Cheong et al. [START_REF] Cheong | Geometric permutations of disjoint unit spheres[END_REF].

We refer the reader to the recent survey by Wenger [START_REF] Wenger | Helly-type theorems and geometric transversals[END_REF] for a broader discussion of geometric transversal theory.

Our results. In this paper we prove Helly-type theorems for line transversals to families of pairwiseinflatable balls in R d . A family F of balls in R d is called pairwise-inflatable if for every pair of balls

B 1 , B 2 ∈ F we have γ 2 > 2(r 2 1 + r 2 2 )
, where r i is the radius of B i , and γ is the distance between their centers. A family of disjoint unit balls is pairwiseinflatable, and so is a family of balls that is "thinly distributed" in Hadwiger's sense. Pairwise-inflatable families of balls are not only more general than families of disjoint congruent balls but allow to generalize most of our proofs obtained in three or four dimensions to arbitrary dimension; the key property, which we prove in this paper, is that the set of pairwiseinflatable families is closed under intersection with affine subspaces, unlike the set of families of disjoint congruent balls.

An order-respecting line transversal to a subset of an ordered family is a line transversal that respects the order induced by the family on that subset. An ordered family F of pairwise-inflatable balls is said to have property (OR)T if it admits a (order-respecting) line transversal. If every k or fewer members of F admit a (order-respecting) line transversal then F is said to have property (OR)T (k). Our first main result requires that the line transversals to the subfamilies induce consistent orderings: Proposition 1 For any ordered family of pairwiseinflatable balls in R d , ORT (2d) implies T and ORT (2d + 1) implies ORT .

We then remove the condition on the ordering at the cost of increasing the Helly number to 4d -1 and restricting ourselves to disjoint unit balls: Proposition 2 For any family of disjoint unit balls in R d , T (4d -1) implies T .

Our results are thus both qualitative and quantitative: we generalize Danzer's result to arbitrary dimension and prove that the Helly number grows at most linearly with the dimension. We build on the work of Holmsen et al. [START_REF] Holmsen | A Hellytype theorem for line transversals to disjoint unit balls[END_REF] who obtained results similar to Propositions 1 and 2 for disjoint unit balls in three dimensions, albeit with larger bounds on Helly numbers (12 and 46 instead of 6 and 11, respectively). A previous version of this paper, also restricted to disjoint unit balls in three dimensions, appeared in the Symposium on Computational Geometry 2005 [START_REF] Cheong | Hadwiger and Helly-type theorems for disjoint unit spheres in R 3[END_REF].

Approach. To prove Proposition 1, we start with a family of balls having property ORT (2d) and continuously shrink them until that property no longer holds, following Hadwiger's approach [START_REF] Hadwiger | Über Eibereiche mit gemeinsamer Treffgeraden[END_REF]. Before the set of order-respecting line transversals to a 2d-tuple of balls disappears (i) it first reduces to a single line and (ii) this line is an isolated line transversal to 2d -1 of the balls. That line has then to be a line transversal to the whole family and Proposition 1 follows; considerations on geometric permutations yield Proposition 2.

Proving the properties (i) and (ii) mentioned above is elementary in the plane but requires considerably more work in higher dimension. For a sequence F, let K(F) ⊂ S d-1 denote the set of directions of line transversals to F. Our proofs rely on the following proposition:

Proposition 3 The directions of order-respecting line transversals to a family of pairwise-inflatable balls in R d form a strictly convex subset of S d-1 . This directly implies property (i) and yields that order-respecting line transversals form a contractible set in line space. From there, a well-known topological analogue of Helly's theorem leads to a weaker version of Proposition 1 sufficient to prove property (ii), namely:

Proposition 4 If a line ℓ is an isolated line transversal to a sequence F of n 2d pairwise-inflatable balls in R d then there exists a subsequence F ′ ⊂ F of size 2d -1 such that ℓ is an isolated line transversal to F ′ .

For the proofs, omitted in this extended abstract, we refer the reader to the full version [START_REF] Cheong | Helly-type theorems for line transversals to disjoint unit balls[END_REF].

Open problems. We conclude by a few open problems suggested by our results.

Problem 1 What is the maximum number of geometric permutations of pairwise-inflatable balls in R d ?

A geometric permutation of a collection of disjoint convex sets is an ordering of these sets that can be realized by a line transversal. To prove Proposition 2 we use the fact that the number of geometric permutations of n disjoint balls in R d is at most 3 if the balls have equal radii [START_REF] Cheong | Geometric permutations of disjoint unit spheres[END_REF]. If the ratio largest radius smallest radius is not bounded independently of n then the number of geometric permutations is known to be Θ(n d-1 ) [START_REF] Zhou | Geometric permutations of balls with bounded size disparity[END_REF].

Problem 2 For which classes of objects is the cone of directions K(A 1 , . . . , A n ) convex, or at least contractible?

Our proof of convexity for the cone of directions of balls collapses for balls that are not pairwiseinflatable. In fact, the set Q F AB is not necessarily convex if B is much smaller than A but very close to it.

Problem 3 For which classes of objects is the set of order-respecting line transversals always connected?

Our proof of Proposition 1 follows from (i) a bounded pinning number and (ii) the fact that as the set of order-respecting line transversals to a sequence disappears it first reduces to a single line. For strictly convex objects, property (ii) follows from the connectivity of the set of order-respecting transversals. Surprisingly, it is an open question whether this set is connected for even 4 disjoint balls in R 3 , whereas it is known to be connected for any triple of disjoint convex objects [START_REF] Goaoc | Structures de visibilité globales : tailles, calculs et dégénérescences[END_REF]Lemma 74]. We conjecture that general convex sets in R d have a bounded pinning number. Thus, understanding how general this connectivity property is would provide insight in how general the example of Holmsen and Matousek [START_REF] Holmsen | No Helly theorem for stabbing translates by lines in R d[END_REF], convex sets whose translates do not admit a Hadwiger theorem, actually is. Of course, a positive answer to Problem 2 for a particular family of convex sets implies a positive answer to Problem 3 for that family as well.

Problem 4 Is the pinning number of disjoint unit balls in R d equal to 2d -1? Surprisingly, the only known lower bound on the Helly number is the construction done by Hadwiger fifty years ago. Note that the bound in our Hadwiger theorem has to be higher than the pinning number of the corresponding family and one can therefore look for a lower bound on the pinning number. Intuitively, considerations on the dimension suggest that the pinning number in dimension d cannot be less than 2d -1, the dimension of the underlying line space being 2d -2.

Acknowledgments

We thank Gregory Ginot, Günter Rote and Guillaume Batog for helpful discussions.


In this paper, a new multilayer six-port circuit using ultra-wideband directional coupler is presented and implemented. The use of the multilayer technology allows having a compact circuit and a very large bandwidth. To validate this concept, a six-port prototype was fabricated and measured.

Simulation and measurement results show the proposed six-port circuit can easily operate over an ultra-wide band from 4 to 7 GHz.

Introduction: During recent years, there was a great interest in six-port technology due to its broad range of applications. Firstly, the six-port circuit has been well known for its ability to perform accurate low-cost microwave measurements of reflection coefficients of microwave networks [START_REF] Tatu | Direction-of-arrival estimation method based on six-port technology[END_REF]. In this area, the six-port circuit was firstly used as a low cost alternative to a vector analyzer.

Secondly, the six-port technique was also applied to low-cost communication direct receivers [START_REF] Hon | RF and Microwave Circuit Design /or Wireless Communications[END_REF][START_REF] Li | Computer and Measurement Simulation of a New Digital Receiver Operating Directly Millimeter-Wave Frequencies[END_REF], which are less complex and allow a higher integration level compared to conventional heterodyne receivers [START_REF] Abe | Direct Conversion Receiver MMIC Based on Six-port Technology[END_REF].

Several six-port circuits with various configurations have been presented and examined [START_REF] Tatu | Ka-band analog front-end for software-defined direct conversion receiver[END_REF][START_REF] Xu | Analysis and implementation of six-port software-defined radio receiver platform[END_REF][START_REF] Zhao | Multi(Six)-port impulse radio for ultra-wideband[END_REF]. However, these structures are implemented using a single-layer Ultra-wideband CPW Six-port Circuits Based on Multilayer Technology Mourad Nedil and Tayeb A. Denidni and Halim Boutayeb substrate or a waveguide structure, which have a limited bandwidth and a large size.

To resolve these problems, a new two-layer conductor-backed coplanar waveguide (CB-CPW) six-port circuit was designed and fabricated. With this multilayer technology, the proposed design allows achieving high performances in terms of low loss and ultra wideband. In addition, by using a multilayer structure, the proposed six-port circuit allows to avoid cross lines compared to single-layer structures [START_REF] Akkaraekthalin | Conductor-backed coplanar waveguide directional coupler and its use for a varactor-tuned 90° phase shifter[END_REF]. To demonstrate the performance of the six-port circuit, an experimental prototype was fabricated and measured. The simulation and measured results are presented and discussed in the next sections. Fig. 2 shows the proposed multilayer six-port. This six-port uses four slotcoupled directional couplers [START_REF] Nedil | Quasi-Static analysis of a new wideband directional coupler using CPW multilayer technology[END_REF]. The solid lines show the CPW lines on the top side and broken lines show the CB-CPW lines on the bottom side.

Six-port circuit design

However, in the CB-CPW technology, the main drawback is the parallel-plate modes, which are considered as unwanted bulk modes [START_REF] Haydl | On the Use of Vias in Conductor-Backed Coplanar Circuits[END_REF]. The minimum parasitic resonance frequency from the parasitic parallel-plate modes of the CB-CPW, which can be predicted, based on a simple rectangular patch theorem [START_REF] Haydl | On the Use of Vias in Conductor-Backed Coplanar Circuits[END_REF] as illustrated in the following equation:

2 2 2 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = g g r mn L n W m c f ε (1)
where c is the velocity of light, ε r is the relative permittivity, and where W g (= 9 mm) and L g (= 15 mm) are the width and length of the ground of the coupler as shown in Fig. 1. Using the above equation, the lowest order mode resonance frequency f 11 of 13.6 GHz is calculated. This parasitic resonance frequency has been shifted to a higher frequency regime. In this case, it can be noted that the leaky wave phenomenon does not affect the performance of the proposed sixport junction, which allows avoiding the use of via in the circuit.

The problem met during the six-port design coupler [START_REF] Nedil | Quasi-Static analysis of a new wideband directional coupler using CPW multilayer technology[END_REF], is related to the fact that the amplitude imbalance is serious between the coupled and direct ports of the six-port structure. The value of the imbalance is up to 3dB, and this is not appropriate for six-port applications. For this raison, we have reduced the coupling between the direct and coupled port of the coupler to obtain equal power splitting within the passband. With IE3D software, an optimization was carried out to determine the optimal values of the coupler dimensions, which are: G=2.8 mm, S=1 mm, W=5.5 mm and L=12 mm.

Results and discussion:

The six-port junction circuit was fabricated using a Rogers RT/Duroid 5880 substrate with a dielectric constant of ε r =2.2 and a thickness of h=0.254 mm. Using an HP8722 network analyzer, the S-parameters of the prototype were measured. Fig. 3 shows the simulated and measured S-parameters of the proposed six-port junction. It can be noted that the return loss is lower than 25 dB over the entire operating frequency band (4-7 GHz). It is found that the simulated and measured results are well matched, and the transmission coefficients are close to the theoretical predicted value of 6 dB.

From, these results, it can be concluded that the proposed six-port provides a bandwidth from 4 to 7 GHz (55%).

Phase difference 3= Phase(S (1, 8)) -Phase(S (1, 7))

The phase difference of the output ports over the operating frequency band is close to the simulated ones, which confirm the proposed concept.

Conclusion:

In this letter, a multilayer compact CPW six-port circuit has been designed and implemented using broadside CPW slot-coupled couplers. The obtained results show clearly that the two-layer six-port has a reduced size compared to conventional single-layer ones and it provides a very large bandwidth from 4 to 7 GHz. The performances in terms of magnitude and phase shift of the proposed six-port are very promising. This six-port has a small volume, light weight, and it ease of fabrication. With these features, the proposed circuit can be used for applications in UWB communication systems.

:

  Basically, the six-port circuit is a passive linear device composed of four couplers and a phase shifter. The block diagram of the standard six-port junction is shown in Fig. 1. It has two inputs and four outputs connected at power detectors. The output signals are functions of the two RF input signals. As a result, complex impedance or phase measurements can be obtained by simple power measurements at the four outputs.

Fig. 4

 4 Fig.4illustrates the simulated and experimental results of the phase shift of the

Fig. 1 :Fig. 2 :Fig. 3 :Fig. 4 :Fig. 3 :Fig. 3 :Fig. 4 :

 1234334 Fig. 1: Block diagram of the proposed six-port junction.


Michele Martone

Luigi Iapichino

Nicolay Hammer

Julia Lawall

Automating Data Layout Conversion in a Large Cosmological Simulation Code

Intro: The Gadget cosmological code

• Large-scale structure formation (galaxies and clusters) • Publicly available [1], cosmological TreePM N-body + SPH code • MPI/OpenMP-parallel; up to O(100k) Xeon cores (SuperMUC@LRZ) • Several teams and several versions (>200 kLoC each)

Figure 1: Galaxies simulated with Gadget -courtesy Magneticum Project [START_REF]Magneticum Home page (large-scale project based on Gadget)[END_REF] / http://magneticum.org

Optimization study of Gkernel

• Gkernel is:

isolated representative Gadget code kernel ("halo finder") stand-alone application, avoids simulation overhead • Node-level optimization study [3] in the frame of the IPCC [START_REF]Intel Parallel Computing Center: LRZ webpage[END_REF] • Target computing systems:

-Knights Corner (KNC), Ivy Bridge (IVB) -Haswell (HSW), Broadwell (BDW), Knights Landing (KNL) • Main changes:

-Data layout optimization -Better threading parallelism

Data layout optimization

From Array of Structures to Structure of Arrays (AoS ⇒ SoA)

• Sample code changes in Fig. 3 and Fig. 4 • Leads to better memory access

• Eases compiler auto-vectorization

• SoA-specific performance benefit (over OpenMP improvement): Notice that i could be any expression.

+ 13% on IVB + 48% on KNC

Perspective for Gadget

Obtained and validated performance guidelines for Gadget

• Limitations of [3] study: • DefSoaStructs: define struct type with arrays instead of scalars each member might depend on #ifdef... • specification language inspired from UNIX patch (SmPL)

-
• SmPL can express steps in Fig. 5, enables Fig. 7 work style

• originally for collateral evolutions in the Linux kernel • arbitrary C language transformations possible, model checking 1 @@ 2 identifier id ,I; 3 type T; 4 @@ 5 struct id { ...

Possible future work

• new performance studies possible • rules for OpenMP optimizations backport [3] • MPI-specific glue code

Figure 2 :

 2 Figure 2: Tests on one-socket Xeon systems; 240 threads (4 thr./core) for KNC; 128 threads (2 thr./core) for KNL. Performance improvement: up to 19x faster on KNL; 13.6x on KNC, ca. for 2-5x on Xeon.

Figure 3 :

 3 Figure 3: A "Structure of Arrays" struct definition introduction example. Only a dozen arrays have been introduced this way in Gkernel. Gadget would need over a hundred.

Figure 4 :

 4 Figure 4: AoS to SoA transition sample. Impacts a few hundreds statements in Gkernel. Would impact many thousands in full Gadget.Notice that i could be any expression.

Figure 5 :

 5 Figure5: Transformation steps, ordered so that their introduction does not break code. The Gkernel study has performed this on a subset of Gadget ([3]).

Figure 7 :

 7 Figure 7:Tool-assisted automatic data layout transformation would greatly accelerate cycles of development and empirical performance optimization.

Figure 9 :

 9 Figure 9: Semantic patch example for AosToSoa, cf. Fig. 4. This patch requires no context apart from the elements to be replaced. Notice also introduction of a new identifier at line 5, used at line 8.

Figure 10 :

 10 Figure 10: Semantic patch composed by four rules. This is similar to how DefSoaFuncs and CallSoaFuncs rules might look like. The first rule (line 1) matches a structure, the second (line 10) introduces an empty function, the third (line 16) populates it, the fourth (line 24) calls it. Notice inheritance of elements across rules, e.g. on line 11.


Hazel Everett
email: hazel.everett@loria.fr

Sylvain Lazard
email: sylvain.lazard@loria.fr

Giuseppe Liotta
email: liotta@diei.unipg.it

Stephen Wismath
email: wismath@cs.uleth.ca

Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices ⋆

This paper shows that any planar graph with n vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that any number of planar graphs admit a simultaneous embedding without mapping with at most one bend per edge.

Introduction

Let S be a set of m distinct points in the plane and let G be a planar graph with n vertices (n m). A point-set embedding of G on S is a planar drawing of G such that each vertex is drawn as a point of S and the edges are drawn as poly-lines. The problem of computing point-set embeddings of planar graphs has a long tradition both in the graph drawing and in the computational geometry literature (see, e.g., [START_REF] Gritzmann | Embedding a planar triangulation with vertices at specified points[END_REF][START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF][START_REF] Pach | Embedding planar graphs at fixed vertex locations[END_REF]). Considerable attention has been devoted to the study of universal sets of points. A set S of m points is said to be h-bend universal for the family of planar graphs with n vertices (n m) if any graph in the family admits a point-set embedding onto S that has at most h bends along each edge.

Gritzman, Mohar, Pach and Pollack [START_REF] Gritzmann | Embedding a planar triangulation with vertices at specified points[END_REF] proved that every set of n distinct points in the plane is 0-bend universal for the all outerplanar graphs with n vertices. De Fraysseix, Pach, and Pollack [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF] and independently Schnyder [START_REF] Schnyder | Embedding planar graphs on the grid[END_REF] proved that a grid with O(n 2 ) points is 0-bend universal for all planar graphs with n vertices. De Fraysseix et al. [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF] also showed that a 0-bend universal set of points for all planar graphs having n vertices cannot have n + o( √ n) points. This last lower bound was improved by Chrobak and Karloff [START_REF] Chrobak | A lower bound on the size of universal sets for planar graphs[END_REF] and later by Kurowski [START_REF] Kurowski | A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs[END_REF] who showed that linearly many extra points are necessary for a 0bend universal set of points for all planar graphs having n vertices. On the other hand, if two bends along each edge are allowed, a tight bound on the size of the point-set is known: Kaufmann and Wiese [START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF] proved that every set of n distinct points in the plane is 2-bend universal for all planar graphs with n vertices.

d d' v v v v v v 5 4 3 2 1 0 (a)
In this paper we study the minimum size of a universal set of points for all planar graphs with n vertices under the assumption that at most one bend per edge is allowed in the point-set embedding. We prove the following theorem.

Theorem 1. Let F n be the family of all planar graphs with n vertices. There exists a set of n distinct points in the plane that is 1-bend universal for F n .

The proof is constructive; an example is shown in Figure 1. We define a set S of n points and show how to compute an embedding of any planar graph with n vertices on S such that the resulting drawing has at most one bend per edge. The drawing procedure starts by computing a special type of book embedding defined in Section 2, and then uses this book embedding to construct the pointset embedding with the algorithm described in Section 3.

Our universal set of n points can be defined either (i) with algebraic coordinates such that they are the vertices of a convex chain with unit-length edges or (ii) on a regular grid of size n2 n by n. In the former case all planar graphs of F n can be drawn on that point set with all bend-points and vertices in a square of size n by n at distance at least 1 2d apart, where d is the maximum degree of the graph. In the latter case, the graphs can be drawn with all bend-points on the grid points of the n2 n by n grid.

We conclude this introduction by noting a result that is immediately implied by Theorem 1. Two planar graphs G 1 and G 2 with the same set of vertices are said to admit a simultaneous embedding without mapping if there exists a set of points in the plane that supports a point-set embedding of both G 1 and G 2 [START_REF] Braß | On simultaneous planar graph embeddings[END_REF]. It is not known whether any two planar graphs admit a simultaneous embedding without mapping such that all edges are straight-line segments. A consequence of [START_REF] Gritzmann | Embedding a planar triangulation with vertices at specified points[END_REF] is that a planar graph has a straight-line simultaneous embedding without mapping with any number of outerplanar graphs. A consequence of [START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF] is that any two planar graphs have a simultaneous embedding without mapping such that each edge is drawn with at most two bends. Theorem 1 implies the following.

Corollary 1. Any number of planar graphs sharing the same vertex set admit a simultaneous embedding without mapping with at most one bend per edge.

Monotone Topological Book Embeddings

Consider the Cartesian coordinate system (O, x, y) and let p, q be two points in the plane. We say that p is left of q and we denote it as p < q if the x-coordinate of p is less than the x-coordinate of q; we shall also use the notation p q to mean that either p is left of q or p coincides with q; we define similarly p > q and p q. A spine is a horizontal line. Let ℓ be a spine and let p, q be two points of ℓ. Let p < q and let b be a point of the perpendicular bisector of pq, at positive distance from ℓ. An arc connecting p to q, denoted as (p, q), is a polygonal chain consisting of two segments: segment pb and segment bq. Point p is the left endpoint of (p, q), point q is the right endpoint of (p, q), and point b is the bend-point of (p, q). Arc (p, q) can be either in the half-plane above the spine or in the half-plane below the spine (such half-planes are assumed to be closed sets); in the first case we say that the arc is in the top page of ℓ, otherwise it is in the bottom page of ℓ. From now on, when we denote an arc as (p, q) we shall implicitly assume that p is its left endpoint.

Let G = (V, E) be a planar graph. A monotone topological book embedding of G, denoted Γ , is a planar drawing such that all vertices of G are represented as points of a spine ℓ and each edge is either represented as an arc in the bottom page, or as an arc in the top page, or as a poly-line that crosses the spine and consists of two consecutive arcs. Let e = (u, v) be an edge of a monotone topological book embedding that crosses the spine at a point d; assuming that u is left of v along the spine, e is such that: (i) u < d < v, (ii) arc (u, d) is in the bottom page, and (iii) arc (d, v) is in the top page. Point d is called the spine crossing of (u, v). Refer to Figure 1(a). Also, let u ′ be the rightmost vertex along the spine of Γ such that u ′ < d and let v ′ be the leftmost vertex of the spine of Γ such that d < v ′ . We say that u ′ and v ′ are the two bounding vertices of d. We say that d is a proper spine crossing if its bounding vertices u ′ and v ′ are such that u < u ′ < d < v ′ < v. (The spine crossings d and d ′ of Figure 1(a) are both proper and both bounded by v 3 and v 2 ). A monotone topological book embedding is proper if all of its spine crossings are proper. Di Giacomo et al. [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF] proved that, for every planar graph, a monotone topological book embedding exists and can be computed (in linear time in the size of the graph). Since an edge that crosses the spine with a non-proper spine crossing can be replaced by a single arc, we obtain the following lemma.

Lemma 1. Every planar graph has a proper monotone topological book embedding which can be computed in linear time in the size of the graph.

Let now Γ be a proper monotone topological book embedding of a planar graph G. If we insert a dummy vertex for each spine crossing of Γ , we obtain a new topological book embedding Γ ′ such that Γ ′ represents a planar subdivision G ′ of G obtained by splitting with a vertex some of the edges of G. We call the graph G ′ an augmented form of G and the drawing Γ ′ an augmented topological book embedding of G. A vertex of G ′ that is also a vertex of G is called a real vertex of Γ ′ ; a vertex of G ′ that corresponds to a spine crossing of Γ is called a division vertex of Γ ′ . Note that every division vertex of Γ ′ has degree two and that every edge of Γ ′ is either an arc in the top page or an arc in the bottom page. The bounding vertices of a division vertex d of Γ ′ are the two real vertices that form the bounding vertices of the spine crossing corresponding to d in Γ . The following property is a consequence of the planarity of Γ ′ . Property 1. Let a = (u, v) and a ′ = (u ′ , v ′ ) be two distinct arcs of Γ ′ that are in the same page and such that u < u ′ . Then, (i

) u < v u ′ < v ′ or (ii) u < u ′ < v ′ v.

Proof of Theorem 1

We prove Theorem 1 by first defining a family of sets of n points in convex position (Subsection 3.1) and then by describing an algorithm that computes a point-set embedding of any planar graph with n vertices on the n-point element of the family (Subsection 3.2).

Necklaces, Cones, and Bend-lines

Let p 0 be any point on the x-axis strictly left of O and p 1 be any point strictly in the top-left quadrant of p 0 . We construct p i+2 , for 0 i n -2, from p i and p i+1 as follows. Let r i be the projection of p i on the vertical y-axis. Point p i+2 can be chosen anywhere on or below the line through r i and p i+1 and strictly above the horizontal line through p i+1 . Let S be any set of n points defined by the above procedure; we call S a necklace of n points. See Figure 1(b).

The cone of p 0 , denoted as C(p 0 ), is the wedge with apex p 0 and bounded by the vertical half-line above p 0 and by the ray emanating from p 0 and through p 1 . The cone of p i (1 i n -2), denoted as C(p i ), has p i as its apex and is bounded by two rays emanating from p i with directions ----→ p i-1 p i and ----→ p i p i+1 . In what follows we assume that C(p i ) is an open set (0 i n -1).

The bend-line of p i (i > 1) is the relatively-open horizontal segment from p i-1 to the vertical line through p 0 . The following properties follow from the definition of a necklace and can be proved with elementary geometric arguments. Let S = {p 0 , p 1 , . . . p n-1 } be a necklace of n points and let CH(S) be its convex hull. Note that p 0 , . . . , p n-1 are ordered from right to left, i.e., p n-1 < . . . < p 0 . Property 2. Let p h < p t (t > 1) be two points of S and let q be a point on the bend-line of p t . Segments p h q and p t p t-1 intersect in their relative interior. Property 3. Let p h ′ p h < p t (t > 1) be three points of S and let q ′ < q be two points on the bend-line of p t . Segments p h q and p h ′ q ′ do not intersect each other.

Computing 1-bend point-set embeddings

We describe a drawing algorithm, called 1-bend Universal Drawer, that receives as input a planar graph G with n vertices and a necklace S of n points and returns a point-set embedding of G on S such that every edge of G is drawn with at most one bend. Algorithm 1-bend Universal Drawer consists of the following steps.

Step 1: Compute a proper monotone topological book embedding Γ of G and the corresponding augmented proper topological book embedding Γ ′ . Let ℓ be the spine of Γ ′ . Label the real vertices of Γ ′ on ℓ by v n-1 , . . . , v 0 in that order from left to right (i.e., v i < v i-1 ). Map each real vertex v i to point p i of the necklace (0 i n -1).

Step 2: Draw the bends of the arcs of the top page of Γ ′ as follows. For each vertex v i of Γ ′ mapped to point p i (0 i n -1) do the following. Let a i0 , a i1 , • • • , a i(k-1) be the sequence of arcs in the top page of Γ ′ whose right endpoint is v i ; assume that a i0 , a i1 , • • • , a i(k-1) are encountered in this order when going clockwise around v i by starting the tour from a point on ℓ slightly to the left of v i . For each a ij (0 j k -1) do:

-Draw a ray r ij emanating from p i such that: (i) r ij is inside the cone C(p i ) of p i , and (ii) r i(j+1) is to the right of r ij (0 j k -2). -Let v h be the left endpoint of a ij in Γ ′ and b ij the bend-point of a ij . If v h is a real vertex of Γ ′ , draw b ij at the intersection point, q, between r ij and the bend-line of p h (through p h-1 ). 4 Else, if v h is a division vertex of Γ ′ and the two real vertices bounding v h in Γ ′ are v t and v t-1 , draw b ij at the intersection point, q, between r ij and the bend-line of p t .

Step 3: Draw the division vertices of Γ ′ as follows. For each division vertex d of Γ ′ , do the following. Let (v i , d) and (d, v j ) be the two arcs of Γ ′ sharing d such that (v i , d) is in the bottom page and (d, v j ) is in the top page. Let q be the point computed in Step 2 such that q represents the bend of (d, v j ). Draw d at the intersection point between p i q and CH(S).

Step 4: Draw the arcs of Γ ′ as follows. For each arc (u, v) of Γ ′ do the following. Let p u , p v be the points representing u and v along CH(S).

-If (u, v) is an arc in the bottom page, draw it as the chord p u p v .

Fig. 1 .

 1 Fig. 1. (a) A proper monotone topological book embedding. The spine crossings d and d ′ are proper. (b) A necklace of six points. The cone of p0, the cone of p2, the bend-line of p2, and the bend-line of p3 are highlighted. (c) A point-set embedding computed by Algorithm 1-bend Universal Drawer.

If p h and pi are consecutive vertices of S (h -1 = i), the ray rij and the bend-line of p h do not intersect, though their closures intersect at pi. For consistency, we draw bij at this intersection point q = pi. In Step 4, the arc (v h , vi) is drawn as the poly-line consisting of segment p h q followed by qpi, which is reduced to point pi.

⋆ Research supported by NSERC and the MIUR Project "MAINSTREAM: Algorithms for Massive Information Structures and Data Streams". Work initiated during the "Workshop on Graph Drawing and Computational Geometry", Bertinoro, Italy, March 2007. , and in particular to W. Didimo and E. Di Giacomo, for useful discussions.

-If (u, v) is an arc in the top page of Γ ′ , let q be the point computed at

Step 2 that represents the bend-point of (u, v). Draw (u, v) as the poly-line consisting of segment p u q followed by qp v .

Step 5: Let Γ be the drawing computed at the end of Step 4. Compute a drawing of G by removing from Γ those points that represent the division vertices of Γ ′ .

The proof of Theorem 1 is now completed by showing that Algorithm 1-bend Universal Drawer correctly computes a point-set embedding of G on S such that each edge has at most one bend. The idea is to show that the drawing computed at the end of Step 5 maintains the topology of Γ and that the geometric properties of the proper monotone topological book embedding and of the necklace make it possible to point-set embed the graph without edge-crossings and with at most one bend per edge. In particular, we show that Γ is a planar drawing by exploiting Properties 1-3; the proof is however omitted here due to lack of space.

Observe that every real vertex of Γ ′ is drawn as a point of S in Γ . Since Γ does not have edge crossings, removing the division vertices from Γ gives a point-set embedding of G on S. Also, by construction, the two edges incident on a division vertex of Γ form a flat angle, and thus removing the division vertices from Γ does not increase the number of bends. It follows that the drawing computed by Algorithm 1-bend Universal Drawer is a point-set embedding of G on S such that each edge has at most one bend. Therefore, any necklace of n vertices is a 1-bend universal set for all planar graphs having n vertices, which concludes the proof of Theorem 1. We omit here the proofs on the size of the drawings.

Conclusion

We leave as an open problem to find a universal point-set for one-bend drawing of planar graphs in a polynomial-size regular grid.


Otfried Cheong
email: otfried@tclab.kaist.ac.kr.

Hazel Everett

Marc Glisse

Joachim Gudmundsson
email: joachim.gudmundsson@nicta.com.au.

Samuel Hornus
email: hornus@tclab.kaist.ac.kr.

Sylvain Lazard

Mira Lee

Hyeon-Suk Na

Farthest-Polygon Voronoi Diagrams *

Given a family of k disjoint connected polygonal sites of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(n log 3 n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k -1 connected components, but if one component is bounded, then it is equal to the entire region.

Introduction

Consider a family S of geometric objects (called "sites") in the plane. The farthest-site Voronoi diagram of S subdivides the plane into regions, each region associated with one site P ∈ S, and containing those points x ∈ R 2 for which P is the farthest among the sites of S.

While closest-site Voronoi diagrams have been studied extensively [START_REF] Aurenhammer | Voronoi diagrams[END_REF], their farthest-site cousins have received somewhat less attention. The case of (possibly intersecting) line segment sites was only solved recently by Aurenhammer et al. [START_REF] Aurenhammer | Farthest line segment Voronoi diagrams[END_REF]; they gave an O(n log n) time algorithm to compute the diagram for n line segments.

Farthest-site Voronoi diagrams have a number of important applications. Perhaps the most wellknown one is the problem of finding a smallest disk that intersects all the sites. This disk can be computed in linear time once the diagram is known, since its center is a vertex or lies on an edge of the diagram. Other applications are finding the largest gap to be bridged between sites, or building a data structure to quickly report the site farthest from a given query point.

We are here interested in the case of complex sites with non-constant description complexity. This setting was perhaps first considered by Abellanas et al. [START_REF] Abellanas | The farthest color Voronoi diagram and related problems[END_REF]: their sites are finite point sets, and so the distance to a site is the distance to the nearest point of that site. Put differently, they consider n points colored with k different colors, and their farthest color Voronoi diagram subdivides the plane depending on which color is farthest away. The motivation for this problem is the one mentioned above, namely to find a smallest disk that contains a point of each color-this is a facility location problem where the goal is to find a position that is as close as possible to each of k different types of facilities (such as schools, post offices, supermarkets, etc.). In a companion paper [START_REF] Abellanas | Smallest color-spanning objects[END_REF] the authors study other color-spanning objects.

The farthest color Voronoi diagram is easily seen to be the projection of the upper envelope of the k Voronoi surfaces corresponding to the k color classes. Huttenlocher et al. [START_REF] Huttenlocher | The upper envelope of Voronoi surfaces and its applications[END_REF] show that this upper envelope has complexity Θ(nk) for n points, and can be computed in time O(nk log n) (see also the book by Sharir and Agarwal [START_REF] Sharir | Davenport-Schinzel Sequences and Their Geometric Applications[END_REF], Section 8.7).

Van Kreveld and Schlechter [START_REF] Van Kreveld | Automated label placement for groups of islands[END_REF] consider the farthest-site Voronoi diagram for a family of disjoint simple polygons. Again, they are interested in finding the center of the smallest disk intersecting or touching all polygons, which they then apply to the cartographic problem of labeling groups of islands.

Their algorithm is based on the claim that this farthest-polygon Voronoi diagram is an instance of the abstract farthest-site Voronoi diagram defined by Mehlhorn et al. [START_REF] Mehlhorn | Furthest site abstract Voronoi diagrams[END_REF]-but this claim is false, since the bisector of two disjoint simple polygons can be a closed curve, see Fig. 1(a). In particular, Voronoi regions can be bounded (which is impossible for regions in abstract farthest-site Voronoi diagrams). Note that the farthest-polygon Voronoi diagram can again be expressed as the upper envelope of k Voronoi surfaces-but this does not seem to lead to anything stronger than near-quadratic complexity and time bounds.

We show in this paper that in fact the complexity of the farthest-polygon Voronoi diagram of k disjoint simple polygons of total complexity n is O(n), independent of the number of polygons. (And in fact we discuss polygonal sites, which are slightly more general than simple polygons, see Section 2.)

When computing closest-site Voronoi diagrams, one makes use of the fact that Voronoi regions surround and are close to their sites. Similarly, in the computation of farthest-site Voronoi diagrams, one makes use of the unboundedness of the Voronoi regions, and often builds up regions from infinity [START_REF] Aurenhammer | Farthest line segment Voronoi diagrams[END_REF]. The difficulty in computing farthest-polygon Voronoi diagrams is that neither of these properties holds: Voronoi regions can be bounded, and finding the location of these bounded regions is the bottleneck in the computation.

We give a divide-and-conquer algorithm with running time O(n log 3 n) to compute the farthestpolygon Voronoi diagram. Our key idea is to build point location data structures for the partial diagrams already computed, and to use parametric search on these data structures to find suitable starting vertices for the merging step. This idea may find applications to the computation of other complicated Voronoi diagrams. Our algorithm implies an O(n log 3 n) algorithm to compute the smallest disk touching or intersecting all the input polygons.

We note that for a family of disjoint convex polygons, finding the smallest disk touching all of them is much easier, and can be solved in time O(n) (where n is the total complexity of the polygons) [START_REF] Jadhav | An optimal algorithm for the intersection radius of a set of convex polygons[END_REF].

Further than the combinatorial bound and the algorithm for constructing the farthest-polygon Voronoi diagram, we also give prove interesting properties of the latter: Voronoi regions can be disconnected, and in fact, the region of a polygon can consist of up to k -1 connected components, but then all components must be unbounded. Also, if the non-empty Voronoi region of polygon P is bounded, then the convex hull of P contains another polygon in its interior and the Voronoi region of P is simply connected.

Farthest-polygon Voronoi diagrams are beautiful, so we invite the reader to examine a few specimens at http://tclab.kaist.ac.kr/∼hornus/fpvd/.

Definition of farthest polygon Voronoi diagrams

We consider a family S of k pairwise-disjoint polygonal sites of total complexity n. Here, a polygonal site of complexity m is the union of m line segments, whose interiors are pairwise disjoint, but whose union is connected. (In other words, the corners1 and edges of a polygonal site form a one-dimensional connected simplicial complex in the plane.) In particular, the boundary of a simple polygon is a polygonal site and we can model a polygon with h holes using its h + 1 boundaries and connecting them with at most h additional edges. For a point x ∈ R 2 , the distance d(x, P ) between x and a site P ∈ S is the distance from x to the closest point on P .

We assume that the family S is in general position, that is, no disk touches four edges, and no two edges are parallel.

The features of a site P are its corners and edges. For a site P ∈ S, we define the function Ψ P : R 2 → R as Ψ P (x) = d(x, P ). The graph of Ψ P is a Voronoi surface, it is the lower envelope of circular cones for each corner of P and of rectangular wedges for each edge of P . The orthogonal projection of this surface on the plane induces a subdivision of the plane, the medial axis M(P ) of P . Each cell C of this subdivision corresponds to a feature w of P , it is the set of all points x ∈ R 2 such that w is or contains the unique closest point on P to x. Here, edges of P are considered relatively open, so the cell of a corner is disjoint from the cells of its incident edges. The boundaries between cells are the arcs and vertices of the medial axis. Since the medial axis of P is the closest-site Voronoi diagram of P 's features, it can be computed in time O(m log m), where m is the complexity of P [START_REF] Fortune | A sweepline algorithm for Voronoi diagrams[END_REF].

A pocket of P is a connected component of CH(P ) \ P , where CH(P ) is the convex hull of P . The medial axis M(P ) contains exactly one tree for each pocket of P . If a pocket shares an edge with CH(P ) that is not an edge of P , then its medial axis tree contains exactly one infinite arc. (There can be additional infinite arcs for each corner of an edge of P that appear on the convex hull.)

We now consider the function Φ : R 2 → R defined as Φ(x) = max P ∈S Ψ P (x). The graph of Φ is the upper envelope of the surfaces Ψ P , for P ∈ S. The surface Φ consists of conical and planar patches from the Voronoi surfaces Ψ P , and the arcs separating such patches are either arcs of a Voronoi surface Ψ P (we call these medial axis arcs), or intersection curves of two Voronoi surfaces Ψ P and Ψ Q (we call these pure arcs). The vertices of Φ are of one of the following three types:

• Vertices of one Voronoi surface Ψ P . We call these medial axis vertices.

• Intersections of an arc of Ψ P with a patch of another surface Ψ Q . We call these mixed vertices.

• Intersections of patches of three Voronoi surfaces Ψ P , Ψ Q , Ψ R . We call these pure vertices.

The projection of the surface Φ onto the plane is the farthest-polygon Voroni diagram F(S) of S. It is a subdivision of the plane into cells, arcs, and vertices. For a point x ∈ R 2 , let us define D(x) = D S (x) as the smallest disk centered at x that intersects all sites P ∈ S. By definition, there is always at least one site that touches D(x) without intersecting its interior, and the radius of D(x) is equal to Φ(x). By our general position assumption, only the following five cases can occur:

• If D(x) touches one site P in only one feature w, and all other sites intersect the interior of D(x), then x lies in a cell of F(S), and the cell belongs to the feature w of P . • If D(x) touches one site P in two or three features, and all other sites intersect the interior of D(x), then x lies on a medial axis arc or medial axis vertex of F(S), and is incident to cells belonging to different features of P . • If D(x) touches one feature w of site P , one feature u of site Q, and all other sites intersect the interior of D(x), then x lies on a pure arc separating cells belonging to features w and u. • If D(x) touches two features of site P and one feature of site Q, and all other sites intersect the interior of D(x), then x is a mixed vertex incident to a medial axis arc of P . • If D(x) touches one feature each of three sites P , Q, and R, and all other sites intersect the interior of D(x), then x is a pure vertex.

Put differently, vertices of F(S) are points x ∈ R 2 where D(x) touches three distinct features of sites. If all three features are on the same site, the vertex is a medial axis vertex. If the three features are on three distinct sites, then the vertex is a pure vertex. In the remaining case, if two features are on a site P , and the third feature is on a different site Q, the vertex is a mixed vertex.

Consider now an arc α of F(S). If we let x move along α, then Φ(x)-which is the radius of D(x)changes continuously. Since the arc is defined by two features (corners or edges), Φ(x) cannot assume a local maximum in the interior of α, but it can assume a local minimum. We denote the location of such a local minimum a pseudo-vertex of F(S). After introducing pseudo-vertices, Φ(x) is a monotone function on each arc, and we can thus orient all arcs in the direction of increasing Φ(x). Fig. 2 illustrates all different vertex types, including the two types of pseudo-vertices of degree two (types (c) and (f)). The top row shows the possible medial axis vertices: types (a) and (b) differ in whether the triangle formed by the three features contains the vertex or not. Similarly, the middle row shows the pure vertex types, with the same distinction between (d) and (e). The bottom row shows the three possible types of mixed vertices. Again, we have to distinguish whether the three features enclose the vertex or not, and in the latter case we need to distinguish which two features are on the same site.

Since the local shape of F(S) around a vertex v is determined solely by the features defining the vertex, in each configuration we can uniquely determine the orientation of the incident arcs. Fig. 2 shows the orientation of these arcs in each case. This orientation plays a crucial role in the next section, where we show that the complexity of the diagram, that is, the total number of vertices, is only O(n).

In addition to the nine types of vertices discussed above, we need to consider vertices at infinity, that is, we consider the semi-infinite arcs of F(S) to have a degree-one vertex at their end. For a vertex v at infinity, the "disk" D(v) is a halfplane, and we have two cases:

• If D(v) touches one site P in two features, and all other sites intersect the interior of D(v), then D(v) is the "infinite" endpoint of a medial axis arc, and we consider it a medial axis vertex at infinity. • If D(v) touches two distinct sites, and all other sites intersect its interior, then D(v) is the "infinite" endpoint of a pure edge, and we consider it a pure vertex at infinity.

Finally, let us define the Voronoi region of a site P ∈ S. The Voronoi region R(P ) of P is simply the union of all cells, medial axis arcs, and medial axis vertices of F(S) belonging to features of P . Voronoi regions are not necessarily connected, in fact, a single Voronoi region can have up to k -1 connected components-we give an example in Section 5.

Complexity bound

Consider again Fig. 2. Let us call a vertex a source if it has more outgoing pure arcs than incoming pure arcs, and a sink if it has more incoming pure arcs than outgoing pure arcs. As shown in the figure, all finite pure vertices are sources. The pure vertices at infinity are sinks. The only other sinks are the mixed vertices of type (g) and (h). Note that mixed vertices of type (i) are neither sources nor sinks.

We can now partition the pure arcs of F(S) into disjoint directed paths. Each such path starts at a source, and ends at a sink. This implies that we can bound the number of sources by twice the number of sinks, as at most two paths can end in a sink.

We show in the following that the number of pure vertices at infinity is at most 2k -2, and that the number of mixed vertices is O(n). Since the total number of vertices of all medial axes M(P ), for P ∈ S, is O(n), this implies the main theorem of this section:

Theorem 1 The complexity of the farthest-polygon Voronoi diagram of a family of disjoint polygonal sites of total complexity n is O(n).

We first discuss the number of vertices at infinity.

Lemma 2

The number of pure vertices at infinity of F(S) is at most 2k -2. The total number of vertices at infinity of F(S) is O(n).

Proof. For two sites P, Q ∈ S, consider the diagram F({P, Q}). A pure vertex at infinity corresponds to an edge of CH(P ∪ Q) supported by a corner of P and a corner of Q. But CH(P ∪ Q) can have at most two such edges, since P and Q are disjoint and both are connected, and so F({P, Q}) has at most two pure vertices at infinity.

Consider now again F(S), and let σ(S) denote the sequence of sites whose Voronoi regions appear at infinity in circular order, starting and ending at the same region. We claim that σ(S) is a Davenport-Schinzel sequence of order 2, and has therefore length at most 2k -1 [START_REF] Sharir | Davenport-Schinzel Sequences and Their Geometric Applications[END_REF]. Indeed, σ(S) has by definition no two consecutive identical symbols. Assume now that there are two sites P and Q such that the subsequence P QP Q appears in σ(S). If we delete all other sites, then sigma({P, Q}) would still need to contain the subsequence P QP Q, and therefore F({P, Q}) would contain at least three pure vertices at infinity, a contradiction to the observation above.

It now suffices to observe that the pure vertices at infinity are exactly the transitions between consecutive Voronoi regions, and their number is at most 2k -2.

All remaining vertices at infinity are medial axis vertices. Since the total complexity of all M(P ), for P ∈ S, is O(n), the bound follows.

It remains to show that the total number of mixed vertices is O(n). Consider a site P ∈ S of complexity m. Its medial axis M(P ) has complexity O(m), and we can consider M(P ) as a graph embedded in R 2 \P . It consists of a collection of trees. In Lemma 4 below we show that for each tree T of M(P ) the intersection T ∩ R(P ) is a connected subtree. Since the mixed vertices on T are exactly the finite leaves of this subtree, this implies that the number of mixed vertices on M(P ) is O(m). Summing over all P ∈ S then proves that the number of mixed vertices of F(S) is O(n).

It remains to prove Lemma 4. We need another notation: for a point x ∈ R 2 and a site P , let D P (x) denote the largest disk centered at x whose interior does not intersect P (and which is therefore touching P ). Note that a point x ∈ M(P ) is in R(P ) if and only if D S (x) = D P (x), which is true if and only if all other sites intersect the interior of D P (x).

Lemma 3 Let γ be a path in M(P ), let Q ∈ S \ {P } be another site, and let γ Q be the set of points x ∈ γ where D P (x) intersects Q. Then γ Q is a connected subset of γ, that is, a subpath.

Proof. We can assume γ to be a maximal path in T , connecting a corner w of P with another corner u (or possibly going to infinity). Assume for a contradiction that there are points x, y, z on γ in this order such that x, z ∈ γ Q , but y ∈ γ Q .

The disk D P (y) separates one connected component of R 2 \ P into two components A and B. The two endpoints of γ must lie in different components, say w ∈ A and u ∈ B.

We first argue that any disk D that does not intersect P cannot contain points in both A and B. Indeed, the boundary of D would have to intersect the boundary of D P (y) in four points, a contradiction.

The disk D P (z) touches P on the boundary of B, and so it contains a point in B-which implies that it cannot contain a point in A. Since D P (y) does not intersect Q and Q is connected, this implies that Q is entirely contained in B. On the other hand, the disk D P (x) touches P on the boundary of A, and by our claim that means that it cannot intersect B. That implies that D P (x) ∩ Q is empty, and the claim follows.

Lemma 4 Let T be a tree of M(P ). Then T ∩ R(P ) is a connected subtree of T .

Proof. Pick two p, q ∈ T ∩ R(P ), let γ be the path on T from p to q, and let x be any point between p and q on γ. We need to show that x ∈ R(P ), which is equivalent to showing that every site Q = P intersects the interior of D P (x). Let Q be such a site. Since p, q ∈ R(P ), Q intersects the interior of D P (p) and D P (q). By Lemma 3 this implies that Q intersects the interior of D P (x).

Computing the Voronoi diagram

The proof of Theorem 1 suggests an algorithm for computing the diagram by tracing the paths considered there. This is roughly equivalent to computing the surface Φ by sweeping a horizontal plane downwards, and maintaining the part of Φ above this plane. This is essentially the approach used by Aurenhammer et al. [START_REF] Aurenhammer | Farthest line segment Voronoi diagrams[END_REF] for the computation of farthest-segment Voronoi diagrams. It does not seem to work for our diagram because of the mixed vertices of type (h), where Φ has a local maximum.

We instead offer a divide-and-conquer algorithm.

Theorem 5 The farthest polygon Voronoi diagram F(S) of a family S of disjoint polygonal sites of total complexity n can be computed in expected time O(n log 3 n).

Proof. Let S = {P 1 , . . . , P k }, and let n i be the complexity of P i . If k = 1, then F(S) is simply the medial axis M(P 1 ), which can be computed in time O(n log n) [START_REF] Fortune | A sweepline algorithm for Voronoi diagrams[END_REF]. Otherwise, we split S into two disjoint families S 1 , S 2 as follows:

• If there is a site P i with complexity n i n/2, then S 1 = {P i } and S 2 = S \ {P i }.

• Otherwise there must be an index j such that n/4 j i=1 n i 3n/4. We let S 1 = {P 1 , . . . , P j } and S 2 = {P j+1 , . . . , P k }.

We recursively compute F(S 1 ) and F(S 2 ). We show below that we can then merge these two diagrams to obtain F(S) in time O(n log 2 n), proving the theorem. It remains to discuss the merging step. We are given a family S of disjoint polygonal sites of total complexity n, and we are given F(S 1 ) and F(S 2 ), where S = S 1 ∪ S 2 is a disjoint partition of S.

Consider the diagram F(S) to be computed. We color the Voronoi regions of F(S) defined by sites in S 1 red, and the Voronoi regions defined by sites in S 2 blue. A pure arc of F(S) is red if it separates two red regions, and blue if it separates two blue regions. The remaining pure arcs, which separate a red and a blue region, are called purple. A vertex of F(S) is purple if it is incident to a purple arc. We observe that by our general position assumption, every finite purple vertex is incident to exactly two purple arcs, and so the purple arcs form a collection of open and closed chains, see Fig. 2.

Merging F(S 1 ) and F(S 2 ) can be done in linear time once all purple arcs are known. In fact, the diagram F(S) consists of those portions of F(S 1 ) lying in the red regions of F(S), and those portions of F(S 2 ) lying in the blue regions of F(S), see Fig. 3.

We show below that if we have a starting vertex on every purple chain, then we can trace the purple chains in total time O(n). For the open chains, we can use the purple vertices at infinity as starting vertices, as these are easy to compute. For the closed purple chains, we make use of the following lemma:

F(S 2 ) Purple curves F(S 1 )
F(S)

Figure 3: Merging F(S 1 ) and F(S 2 ) to obtain F(S).

Lemma 6 Any closed purple chain contains a mixed vertex.

Proof. A closed purple chain is a compact set in the plane, and so Φ(x) assumes a maximum in some point x on this curve. But Φ can assume a local maximum only in mixed vertices of type (g) and (h), see Fig. 2.

It remains to discuss the following three steps:

• Computing the pure vertices at infinity.

• Computing the mixed vertices.

• Tracing the purple chains.

Tracing the purple chains

We first need to discuss a monotonicity property of cells of F(S). Let C be a cell of F(S) belonging to feature w of site P . For a point x ∈ C, let x * be the point on w closest to x. Let f x be a directed line segment starting at x and extending in direction --→

x * x until we reach M(P ) (a semi-infinite segment if this does not happen). We call f x the fiber of x. We note that if w is an edge, then all fibers of C are parallel and normal to w; if w is a corner then all fibers are supported by lines through w. Lemma 7 For any x ∈ C, the fiber f x lies entirely in C (and therefore in R(P )).

Proof. The disk D(x) touches P in x * only, and its interior intersects all other sites. When we move a point y from x along f x , the disk D centered at y through x * keeps containing D(x), and it therefore still intersects all other sites. This implies that y ∈ C as long as D does not intersect P in another point. This does not happen until we reach M(P ).

An immediate consequence is that cells are "monotone": Lemma 8 Let C be a cell belonging to feature w. If w is a corner, then any line through w intersects C in a segment. If w is an edge, then any line normal to w intersects C in a segment.

Proof. Consider such a line , and let x be the point closest to w in ∩ C. Then the entire fiber f x lies in C, and no point on beyond the medial axis can be in C.

Lemma 8 implies that the boundary of a cell C belonging to a feature w consists of two chains monotone with respect to w (that is, monotone in the direction of an edge, and rotationally monotone around a corner). The lower chain is closer to the feature and consists of pure arcs only, the upper chain consists of medial axis arcs only.

An important consequence of Lemma 7 for tracing the purple chains is the following:

Lemma 9 Let f x be a fiber of a cell C in F(S 1 ) or F(S 2 ). Then f x is intersected by at most one purple arc of F(S).

Proof. Assume for the contrary that two purple arcs intersect f x in points p and q, where q lies on f p . Then there is a point p on f x very close to p such that p ∈ R(P ) in F(S), where C belongs to site P .

O P 1 P 2 P 3 P 4 1 (φ) = 2 (φ) 3 (φ) 4 (φ) g 1 (φ) = g 2 (φ) g 3 (φ) g 4 (φ)
Figure 4: Constructing the vertices at infinity.

But then the fiber f p lies in R(P ) in F(S), and cannot intersect a purple arc at q.

Lemma 9 allows us to trace purple chains very easily. Once we have located a starting vertex in both F(S 1 ) and F(S 2 ), we trace the chain through both diagrams at the same time. We observe that every time it intersects a cell boundary in F(S 1 ) or F(S 2 ), we have indeed found a vertex of the purple chain, so the total number of such intersections is only O(n).

When we enter a cell C along a purple arc, we simply follow the arc through the cell as it intersects the fibers of C. We consider the upper and lower chain of C at the same time, and trace the cells of F(S 1 ) and F(S 2 ) in parallel. This allows us to charge the cost of tracing to those features of the two cells incident to the fibers the purple chain actually intersects. Since no fiber is intersected by more than one purple arc, the total tracing time is O(n).

Computing the vertices at infinity

This is relatively easy, making use of the same Davenport-Schinzel arguments used in Lemma 2. For site P i ∈ S and angle φ ∈ [0, 2π), let i (φ) be the oriented line with direction φ tangent to P i and leaving P i entirely on its left, see Fig. 4. Let g i (φ) be the signed distance from the origin to i (φ) (positive if the origin lies left of i (φ), negative otherwise). If P i is a polygonal site of complexity m, we first compute the convex hull CH(P i ) in time O(m log m), and can then read off a description of the function g i in time O(m).

We then compute the lower envelope g of the functions g i . The pure vertices at infinity correspond exactly to the breakpoints of this lower envelope. Since two functions g i , g j can intersect at most twice (see the proof of Lemma 2), the lower envelope can be computed in time O(n log n) [START_REF] Sharir | Davenport-Schinzel Sequences and Their Geometric Applications[END_REF].

Computing the mixed vertices

This is the hardest part of the algorithm. We start by computing the randomized2 point-location data structure of Mulmuley [START_REF] Mulmuley | A fast planar partition algorithm[END_REF] (see also [START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF]Chapter 6]) for the two given Voronoi diagrams F(S 1 ) and F(S 2 ). This data structure only needs two primitive operations:

• For a given point p in the plane, determine whether the query point x lies left or right of p; and • For an x-monotone line segment or parabola arc γ, determine whether the query point lies above or below γ.

Both cases can be summarized as follows: Given a comparator γ, determine on which side of γ the query point x lies. The comparator can be either a line or a parabola arc. We compute the mixed vertices lying on each medial axis M(P ) separately. For each tree T of M(P ), the intersection T ∩ R(P ) is a connected subtree by Lemma 4. We can determine the inner vertices of this subtree easily, by performing a point location operation for each vertex v of T in F(S 1 ) and F(S 2 ). p q p q P P C(p, q) q p C(q, p)

p q P P R(P ) (a) (b) (c)
Figure 5: (a) pq is a sub-arc of M(P ). p q is the intersection of pq with R(P ). We also have p q = M(P ) ∩ R(P ). (b) The cylinder C(p, q) of the pair (p, q) in (a). (c) The cylinder C(q, p) of the pair (q, p) for a parabola arc.

This tells us which site is farthest from v-and v lies in R(P ) if and only if this is the site P . Let I be the set of vertices of T that lie in R(P ). We now need to consider two cases.

If I is non-empty, then every arc α of T incident to one vertex in I and one vertex not in I must contain exactly one mixed vertex x * by Lemma 4. We locate this vertex x * by using parametric search along the arc α [START_REF] Megiddo | Applying parallel computation algorithms in the design of serial algorithms[END_REF]. The idea is to execute two point location queries in F(S 1 ) and F(S 2 ) using x * as the query point. Each query executes a sequence of primitive operations, where we compare the (unknown) location of x * with a comparator γ (a line or a parabola arc). This primitive operation can be implemented by intersecting α with γ, resulting in a set of at most four points. In O(log n) time, we can test for each of these points whether it lies in R(P ). This tells us between which of these points the unknown mixed vertex x * lies, and we can answer the primitive operation.

It follows that we can execute the two point location queries in time O(log 2 n), and we obtain the cells C 1 and C 2 of F(S 1 ) and F(S 2 ) containing x * . The mixed vertex x * lies on the bisector of the features w 1 and w 2 to which these two cells belong (one of them is necessarily a feature of P ). We compute the intersection of this bisector with α to obtain x * .

It remains to consider the case where I is empty, that is, no vertex of T lies in R(P ). Nevertheless, the region R(P ) may intersect a single arc α of T , and there are then two mixed vertices on α that we need to find. We first need to identify the arcs of T where this could happen.

Let p and q be two points on the same arc α of M(P ). We define the cylinder C(p, q) of the pair (p, q) as C(p, q) = x∈pq

D P (x) \ D P (p),
where the union is taken over all points x on the arc α between p and q, see Fig. 5. We define a condition G(p, q) as follows: Let Q be a site farthest from p, and let w be a feature of Q closest to p. Then G(p, q) is true if w ∈ C(p, q) or if Q intersects D P (q). We can now prove the following lemma:

Lemma 10 Let p, q be points on the same arc α of M(P ), such that neither p nor q lie in R(P ). If α intersects R(P ) between p and q, then G(p, q) and G(q, p) both hold.

Proof. Since the statement is symmetric, we only need to show G(p, q). Let Q be a site farthest from p, and let x be a point between p and q on α that lies in R(P ). This implies that Q intersects D S (x) = D P (x). Since Q does not intersect D P (p), we deduce that Q intersects C(p, q). If Q does not lie entirely in C(p, q), then it must intersect D P (q), and indeed G(p, q) holds.

Let us call an arc α connecting vertices p and q of T a candidate arc if G(p, q) and G(q, p) both hold.

Lemma 11 If α is a candidate arc of a tree T of M(P ), then all points in T ∩ R(P ) lie on α.

Proof. Let α connecting p and q be a candidate arc. Since G(p, q) holds, there is a site Q = P such that Q does not intersect D S (p), but does intersect C(p, q). In particular, there must be a point x ∈ α such that Q intersects D S (x) ⊃ D P (x). Let now y be a point on T such that the path from q to y goes through α. By Lemma 3, Q cannot intersect D P (y), and so y ∈ R(P ). Symmetrically, since G(q, p) holds, we find that any point z ∈ T such that the path from p to z goes through α cannot be in R(P ), and so any point of T ∩ R(P ) must lie on α.

Lemma 11 implies immediately that if there are two candidate arcs, then T ∩ R(P ) is empty, and there are no mixed vertices on T .

Since we have point-location data structures for F(S 1 ) and F(S 2 ), we can test the condition G(p, q) in time O(log n) for a given arc α in M(P ) and two points p, q ∈ α. This allows to identify all candidate arcs in O(m log n) time, where m is the complexity of T . If there is zero or more than one candidate arcs, we can stop immediately, as there are no mixed vertices on T .

It remains to consider that there is a single candidate arc α in T . We again apply parametric search, using an unknown point x * in α ∩R(P ) as the query point. During the point-location query, we maintain an interval pq on α that must contain x * (if x * exists at all). To implement a primitive query, we must determine the location of x * with respect to a comparator γ. If the current interval pq on α does not intersect γ, we can proceed immediately, otherwise we get a sequence of points p = x 0 , x 1 , x 2 , . . . , x s = q on α, where 2 s 5. We first test if some x i ∈ R(P ) in O(log n) time. If so, we abort the process, and use the method discussed above to find the mixed vertices on the arc between p and x i and between x i and q. If no x i lies in R(P ), we test the conditions G(x i , x i+1 ) and G(x i+1 , x i ) for each consecutive pair. If the conditions hold for no pair or more than one pair, we can stop immediately, as there cannot be a point of R(P ) on α. If there is exactly one pair, we have found the location of x * with respect to the comparator γ, and we continue the point location query.

If both point location queries terminate without encountering a point in R(P ), we have found the cells C 1 and C 2 of F(S 1 ) and F(S 2 ) containing x * . We can then compute a point x ∈ α ∩ R(P ) in constant time, and use again the method above to find the two mixed vertices on α.

Connectedness of Voronoi regions

So far, we have developed the theory of farthest-polygon Voronoi diagrams only as far as we needed it for the complexity bound and the algorithm. In this section, we give two interesting properties on the Voronoi regions. First, we prove that the Voronoi region of a single polygonal site can have k-1 connected components. Second, we prove that a bounded Voronoi region is necessarily (simply) connected.

Lemma 12 A single Voronoi region can have k -1 connected components.

Proof. The construction is shown in Fig. 6. It consists in one (k -1)-regular polygon R and k -1 polygonal chains C 1 , . . . , C k-1 . Let e 1 , e 2 , . . . , e k-1 denote the edges of R in circular order. We inductively construct the polygonal sites C i , i = 1, 2, . . . , k -1 as follows. For a supporting line l of e i , let l + be the closed halfplane containing R and l -be the other. Then, consider the intersection C * i between l + and the four edges of a square that contains R, C 1 , . . . , C i-1 inside. We define C i as the set of points of C * i whose distance to l is larger than some fixed small ε > 0. C i has complexity at most 4. Note that l + contains C i completely. Consider a ray from e i to infinity in l -which is orthogonal to l. Since l - intersects all sites but C i , the infinite endpoint of this ray lies in the region C i = R(C i ) at infinity. On the other hand, for a sufficiently small ε, there is a line l passing through v i (the vertex incident to e i-1 and e i ) such that we can define l + as an open halfplane containing R\{v i } and l -as the other open halfplane intersecting all the other sites but R. The infinite endpoint of the ray from v i to infinity in l - which is orthogonal to l lies in a connected component of R(R), which we call R i .

Therefore at infinity C 1 , R 1 , C 2 , • • • , C k-1 , R k-1 appear in turn. Note that for a point x in the region R(R) of R, its fiber f x is an infinite ray because R is convex. For i = 1, 2, . . . , k = 1, consider the half-line x i ω i from an infinite point ω i ∈ C i to a point x i ∈ R closest to ω i . If x ∈ x i ω i lies in R(R), then f x ⊂ R(R), which is impossible because ω i ∈ C i . Define W = R ∪ i x i ω i (W looks like a hand-drawn sun). We then have W ∩ R(R) = ∅, and R 2 \ W consists in k -1 unbounded connected subsets of the plane. The connected subset bounded by x i ω i , x i+1 ω i+1 and R contains R i completely. It follows that R i = R j when i = j.

We now turn our attention to bounded regions in F(S). Let P be a site of S, whose Voronoi region, R(P ), is bounded and non-empty. We prove that R(P ) is simply connected. Due to space limitation in this extended abstract, we only sketch the following proofs.

Lemma 13 P properly contains a site Q = P inside one of its pockets.

Proof. We first observe that R(P ) contains some points of the medial axis M(P ) of P . Indeed, let x ∈ R(P ) and consider its fiber f x . Since R(P ) is bounded, f x does not extend to infinity and therefore touches M(P ).

Let p be a point in R(P ) ∩ M(P ). If p lies in a bounded pocket of P , then clearly this pocket does contain all the other sites in S \ {P } and the lemma is proved. Otherwise, we let p move along the medial axis M(P ) up to infinity. At some point p * , p gets out of R(P ). This means that D S (p * ) = D P (p * ) is tangent to another site Q without intersecting it properly. We can then argue that the site Q lies in a pocket of P .

Lemma 14 R(P ) is simply connected.

Proof. We first observe that P cannot properly contain two sites in two different pockets. Indeed, in such a case, the region of P is empty, since no disc avoiding P can intersect two of its pockets. But this contradicts our hypothesis that R(P ) is non-empty.

Let P be the pocket of P containing another site. As argued in the proof of lemma 13, it is clear that the tree T of M(P ) is the only tree of M(P ) whose intersection with R(P ) is not empty. By lemma 4, T ∩ R(P ) is a connected sub-tree of T . By letting the points of R(P ) move along their fiber, we can design a (continuous) deformation retraction of R(P ) onto T ∩R(P ) (we omit the details in this extended abstract). Since T ∩ R(P ) is simply connected, so is R(P ).

Figure 1 :

 1 Figure 1: (a) The bisector of two polygons can be a closed curve. (b) The medial axis M(P 1 ). (c) The Voronoi region R(P 1 ). (d) The farthest polygon Voronoi diagram F({P 1 , P 2 }).

Figure 2 :

 2 Figure 2: The different types of vertices in the farthest polygon Voronoi diagram. Pure arcs are shown solid, medial axis arcs dashed. The arrows indicate the direction of increasing Φ(x).

Figure 6 :

 6 Figure 6: The Voronoi region of the middle polygon has k -1 connected components.

We reserve the word "vertex" for vertices of the Voronoi diagram.

This is the only use of randomization in our algorithm. It can probably be avoided by using the point location data structure of Edelsbrunner et al.[START_REF] Edelsbrunner | Optimal point location in a monotone subdivision[END_REF] instead.

Acknowledgments

We thank the participants of the 8th Korean Workshop on Computational Geometry, organized by Tetsuo Asano at JAIST, Kanazawa, Japan, Aug. 1-6, 2005.

* This research was supported by the French-Korean Science and Technology Amicable Relationships program (STAR), and the Brain Korea National ICT Australia is funded through the Australian Government's Backing Australia's Ability initiative, in part through the Australian Research Council.


Juanjo Rué

Dimitrios M Thilikos

Vasiliki Velona

Structure and Enumeration of K 4 -minor-free links and link diagrams

Keywords: series-parallel graphs, links, knots, generating functions, asymptotic enumeration, map enumeration

We study the class L of link types that admit a K 4 -minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K 4 . We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L and subclasses of it, with respect to the minimal number of crossings or edges in a projection of L ∈ L. Further, we enumerate (both exactly and asymptotically) all connected K 4 -minor-free link diagrams, all minimal connected K 4 -minor-free link diagrams, and all K 4 -minor-free diagrams of the unknot.

Introduction

The exhaustive generation of knots and links is a well-established problem in low dimensional geometry (see [START_REF] Menasco | Handbook of knot theory[END_REF]Ch.5], for instance). However, there are very few enumerative results in the literature and they are relatively recent, (see [START_REF] Sundberg | The rate of growth of the number of prime alternating links and tangles[END_REF] and [START_REF] Kunz-Jacques | The asymptotic number of prime alternating links[END_REF]). Moreover, there seems to be no known results connecting graph theoretic classes with link classes.

Let us start with some formal definitions. A knot K is a smooth embedding of the 1-dimensional sphere S1 in R 3 . A link is a finite disjoint union of knots L = K 1 ∪ ... ∪ K n . Two links L 1 and L 2 are equivalent if there is a continuous and injective function h :

R 3 × [0, 1] → R 3 , such that h(L 1 , 0) = L 1 and h(L 1 , 1) = L 2 .
A link equivalent to a set of non intertwined circles is called a trivial link. If it is a knot, we also call it the unknot.

Consider a link L and a sphere S2 embedded in such a way that it meets the link transversely in exactly two points P 1 and P 2 . Then we can discern two different links L 1 , L 2 , after connecting P 1 and P 2 . The first corresponds to the part of L in the interior of the sphere and the second to the part in the exterior. We then call L a connected sum with factors L 1 , L 2 , denoted L 1 #L 2 . A link that does not have non-trivial factors is called prime, otherwise composite. A link is split if there is a sphere embedded in the link complement that separates the link. Each of the components is called a disjoint component of the link and, conversely, the link is their disjoint sum.

Let L ∈ R 3 be a link and let π : R 3 → R 2 be a projection map. If for all x ∈ L, |π -1 (x)| = 2 or 1, and all the double points are finite and transverse, then the projection is said to be regular. For all knots defined here, there exists a regular projection [START_REF] Cromwell | Knots and links[END_REF]Ch. 3]. This allows to work with link-diagrams, i.e. a triple (V, E, σ), where (V, E) is a 4-regular plane graph and σ :

V (G) → E(G)

2

, where, for every v ∈ V (G), σ(v) is a set of two opposite edges of the embedding of G and encodes which pair is overcrossing. Notice that a link-diagram may also have vertexless edges. We call these edges trivial. The crossing number of a link L is the minimum number of crossings that can have a diagram of it. Such a diagram is called minimal. We also say that a diagram (V, E, σ) is K 4 -minor-free if the graph (V, E) does not contain any subgraph that is a subdivision of a K 4 .

A torus link is a link that can be embedded on the torus. They are denoted by T (p, q), p, q ∈ Z, where p and q are the number of times that the link crosses the meridian and the longitude cycle, respectively. Let T 2 be the closure of torus links of type T (2, q), q ∈ Z -{0}, under the connected sum operation. Let L be the class of links that have a K 4 -minor-free link-diagram and mcl(T 2 ) be the closure of T 2 under disjoint sum.

Structure of K 4 -links and enumeration

Our first result gives the type of links that admit a K 4 -minor-free diagram.

Theorem 2.1 The links that admit a K 4 -minor-free diagram are exactly the ones in mcl(T 2 ), i.e. L = mcl(T 2 ).

Based on the above, we derive a precise description of links that admit a K 4 -minor-free diagram. Let L be the class of non-split links in L and L the class of links in L with no trivial disjoint components, with size defined as their crossing number. We will obtain the asymptotic growth of L with respect to the number of edges in a minimal diagram (not the crossing number, so as to account also for trivial disjoint components). Let L(z), L(z), and L(z) be the respective generating functions. Finally, let T be the class of non plane, unrooted trees, where the vertices are labelled with multisets of the set {1} ∪ {±3, ±5, ...} and the edges are labelled with an element of the set {2, ±4, ±6, ...}. These labels will encode crossing numbers, hence a label i corresponds to size |i|. The size of T ∈ T is the sum of its labels. See Figure 1 for an example of such a tree. Using Proposition 2.2 and the framework of the Symbolic Method (see [START_REF] Flajolet | Analytic combinatorics[END_REF]), we derive combinatorial expressions for L that translate to generating functions. Let K and K be the classes of prime knots and composite knots plus the trivial knot in L, respectively. For prime knots in L, i.e. prime torus knots T (2, 2i + 1), i ∈ Z\{0, -1}, it holds that K(z) = 2 i≥1 z 2i+1 = 2z 3 1-z 2 , counting according to their crossing number. For K, it is enough to consider non-empty multisets of prime torus knots, therefore K = MSet ≥1 ( K), which translates to the expression

K(z) = exp k≥1 1 k K(z k ) -1 = exp k≥1 1 k 2z 3k 1 -z 2k -1.
Let G be the class of unrooted and unlabelled non-plane trees. Notice that one cannot replace immediately z for K in the ogf G(z), since the vertices are not distinguishable. Hence, to continue, one needs to use cycle indices. Let G • be the class of rooted and unlabelled non-plane trees. For the cycle index of G • , it is known (see [START_REF] Bergeron | Combinatorial species and tree-like structures[END_REF]) that

Z G • (s 1 , s 2 , ...) = s 1 exp k≥1 1 k Z G • (s k , s 2k , ...) .
Let E be the combinatorial class of the edge labels of T , hence E(z) = z 2 + 2z 4 1-z 2 , and let f (z) = E(z)K(z). We can now obtain the ordinary generating function of F = T • • (E × L c ). By Polya's Theorem, the latter satisfies the equation

F (z) = Z G • (f (z), f (z 2 ), ...). Then, it holds that L(z) = F (z) E(z) + E(z) 2 - F (z) 2 E(z) 2 + F (z 2 ) E(z 2 ) ,
by the Dissymmetry Theorem (see [START_REF] Bergeron | Combinatorial species and tree-like structures[END_REF]). The first terms of L(z) are as follows: L = 1 + z 2 + 2 z 3 + 3 z 4 + 4 z 5 + 9 z 6 + 12 z 7 + 26 z 8 + 40 z 9 + ...

We can then get asymptotic estimates by means of complex analytic tools:

Theorem 2.3 L has asymptotic growth of the form:

[z n ] L(z) ∼ cn -3/2 Γ(-1/2) ρ -n , ρ ≈ 0.44074, c ≈ 1.45557.
Additionally, L has the same type of asymptotic growth with the same ρ and c ≈ 3.61691.

The generating function L(z) is equal to L(z 2 ) 1 1-z , since a link diagram of n vertices has 2n non-trivial edges and a number of trivial edges. We thus obtain the following corollary.

Figure 1 .

 1 Figure 1. An object of T .

The first and the third author have partially been supported by the MINECO projects MTM2014-54745-P, MTM2017-82166-P and the María de Maetzu research grant MDM-2014-0445 (BGSMath). The second author has been supported by the project "ESIGMA" (ANR-17-CE40-0028). The third author has been supported under an FPI grant from the MINECO research project MTM2015-67304-PI.

2 Emails:juan.jose.rue@upc.edu, sedthilk@thilikos.info, vasiliki.velona@upf.edu

Acknowledgement. All authors like to thank Lefteris Kirousis that contributed to the inception of this research.

Corollary 2.4 L has asymptotic growth of the form:

where ρ ≈ 0.44074 and c ≈ 8.97779 or c ≈ 3.95687, depending on whether n is even or odd, respectively.

Finally, we also get asymptotic estimates for the coefficients of K(z). The following result is a consequence of Meinardus' Theorem (see [START_REF] Flajolet | Analytic combinatorics[END_REF]VIII.23]).

Theorem 2.5 K has asymptotic growth of the form:

Enumeration of families of link diagrams

Enumerating connected K 4 -free link-diagrams is equivalent to enumerating 4-regular unrooted planar maps which are K 4 -minor-free, that we call M1 . We first give a construction for the rooted ones, M 1 , with respect to edges, adapting the construction for rooted 4-regular maps in [START_REF] Noy | Enumeration of labeled 4-regular planar graphs[END_REF]. With this we obtain a functional system of equations that can be analyzed by using the analytic machinery developed by Drmota in [START_REF] Drmota | Systems of functional equations[END_REF]. Finally, by adapting an argument by Richmond and Wormald in [START_REF] Richmond | Almost all maps are asymmetric[END_REF], we are able to show that we can unroot the maps under study, showing that the maps in our class with non-trivial automorphisms are exponentially few. This study gives the following result:

Refining the combinatoric analysis in the previous case (with more auxiliary classes) and using again an adaptation of the argument of Richmond and Wormald in [START_REF] Richmond | Almost all maps are asymmetric[END_REF], we are able to asymptotically enumerate also the class of minimal link diagrams M2 , as well as the class of K 4 -free link diagrams of the unknot, M3 :


A Gaufrès

F Husser

E Fourmond

R Monna

M Lemiti

USE OF AMORPHOUS HYDROGENATED SILICON CARBIDE AS A REAR-SIDE PASSIVATION LAYER FOR CRYSTALLINE SILICON SOLAR CELLS

Keywords: PERC, passivation, metallic contact, co-firing

a-SiC x :H is a material which could be used as a passivating layer for a crystalline silicon solar cell with a minimum surface recombination velocity of 7.5 cm.s -1 . The thermal stability should also be considered. As the Sirichest a-SiC x :H films are the less stable one, carbon-richer stoichiometry are preferred. From C(V) measurements, the interface between a-SiC x :H and c-Si seems to be in accumulation regime. In presence of local aluminium contacts, it means that a BSF on the whole rear side is established making the use of a-SiC x :H interesting for the rearside passivation. For the PERC solar cells, two stoichiometries [C] = 0.15 and [C] = 0.24 are chosen because they are more thermally stable than Si-richest films and they ensure good surface passivation. An additional layer of SiN x :H at the rear side improves the internal reflection. We compare also results obtained with solar cells schemes with and without thin layer of oxide at the front-side.

INTRODUCTION

The reduction of the cost of fabrication of silicon solar cells is a challenging question for the competitiveness of solar energy because it involves the limitation of the quantity of raw materials. The thickness of the solar cell is reduced and the aspect ratio increases, which intensifies the impact of the surface properties over the volume ones. The importance of the surface passivation of the solar cell is thus enhanced. In this work, we investigate the use of amorphous hydrogenated silicon carbide (a-SiC x :H) as a passivating layer for the rear side of a PERC structure. Janz et al. [START_REF] Janz | 21 st European Photovoltaic Solar Energy Conference[END_REF] have deposited a Sirich passivating layer of a-SiC x :H. Problems of hydrogen effusion which affect solar cell performances have been observed. Riegel et al. [START_REF] Riegel | Proc. of 25th European PVSC[END_REF] enhanced the loss of quality of local contacts in a PERC structure between silicon and aluminum reducing the fill-factor. Despite this problem, better results than a standard configuration with Al-BSF have been obtained. Si-rich a-SiC x :H may be passivating, but its refractive index is close to the c-Si one. In order to optimize internal reflection, Glunz et al. [START_REF] Glunz | 20 th European Photovoltaic Solar Energy Conference[END_REF] have added a C-rich layer with a lower refractive index with a gain of 2% efficiency. A stack of a-SiC x :H and oxide layers gives similar results [START_REF] Suwito | 24 th European Photovoltaic Solar Energy Conference[END_REF]. Our work consists to investigate the passivating properties of a-SiC x :H depending on stoichiometry at the rear-side of PERC solar cell structures compared to a standard cell configuration.

PECVD DEPOSITION PROCESS

a-SiC x :H have been deposited using a semi-industrial low-frequency PECVD reactor (440 kHz) elaborated by Semco Engineering [START_REF] Dupuis | [END_REF]. The plasma is pulsed. The experimental parameters are fixed to ensure good homogeneity of deposited layers throughout the 15 capacitive electrodes assembled in a vertical configuration. The deposition parameters are presented in table 1. In the literature, most of the reactors use highfrequency, because of a better surface passivation properties, but low-frequency reactors are also of interest since the hydrogenation of the silicon substrate is more efficient [START_REF] Yelundur | 19 th European Photovoltaic Solar Energy Conference[END_REF]. Precursor gases are silane (SiH 4 ) and methane (CH 4 ) for a-SiC x :H and silane and ammoniac (NH 3 ) for SiN x :H. The different layers are referred according to their carbon content [C] (at. %), defined as :

(1)

3 PASSIVATING PROPERTIES OF a-SiC x :H LAYERS a-SiC x :H layers are deposited on both n-and p-type c-Si wafers, Float-Zone quality, (100)-oriented with a resistivity comprised between 2 to 5 Ω.cm, and bulk lifetime close to 6ms. The samples were cleaned before deposition using CARO chemical cleaning followed by an HF dip. The tested stoichiometries of a-SiC The surface recombination velocity of a-SiC x :H is extracted from the effective lifetime obtained by QSS-PCD method [START_REF] Sinton | [END_REF] at an injection level of 1.10 15 cm -3 , with a Sinton Consulting WCT-100 apparatus [8]. The tendency of the experimental points is similar between both substrate doping types, which is not a determining parameter of the passivation. The Si-rich films are the more passivating ones with a minoring surface recombination velocity of 7.5 cm.s -1 for p-type c-Si and 11 cm.s -1 for n-type c-Si.

The thermal stability of the films is tested with a Rapid Thermal Annealing (RTA). Two anneals at 500 °C and 800 °C are compared. All the samples annealed at 800 °C have lost their passivating properties. The Sirichest films are the most degraded because of the effusion of hydrogen atoms and then the increase of the concentration of dangling bonds at the interface between c-Si and a-SiC x :H. The annealing at 500 °C maintains the passivating properties of the layers, for [C] = 0.15, [C] = 0.24 and [C] = 0.37. For high-temperature step in the manufacturing process, a compromise should be done between the lifetime results and the thermal stability.

To have a low enough surface recombination velocity is an important condition for the use of a material as a passivating layer for not sufficient for the rear side. The most convincing example is the SiN x :H whose the positive fixed charge density induces "parasitic" shunt effect located at the aluminum contacts and reducing the short-circuit current [9]. The nature of the fixed charges is important to determine in case of a-SiC x :H in order to know if it matches with the rear-side passivation condition. C(V) measurements have been realized on samples with the same quality of c-Si. A mercury-probe contact is used as metallic contact (metal/a-SiC x :H/c-Si structure). The experimental data are fitted with the Nicollian & Brews model described in [8] as we had difficulties to obtain complete C(V) curves because of the leaky nature of a-SiC x :H. With local aluminum contacts, we would have an extended BSF to the whole rear face. This result is thus an argument for using a-SiC x :H as a rear-side passivation layer.

PERC SOLAR CELL EXPERIMENT

16 p-type Cz-Si 156x156 cm 2 wafers with a resistivity of 1-3 Ω.cm are used for solar cells production. The emitter has a resistance of 70 Ω/sq. A thin layer of oxide is grown after emitter formation on front side. This improves the passivation of the emitter and the opencircuit voltage also increases slightly. The thickness of oxide is limited to about 10 nm and the thickness of SiN x :H is then adapted to limit the increase of reflectivity (0.5 % greater). The manufacturing process of our PERC solar cells is described on Figure 3. The antireflective SiN x :H is deposited at CEA-INES in a reactor at 40 kHz. The rearside a-SiC x :H and SiN x :H layers are deposited with the PECVD equipment at INL. As the more passivating a-SiC x :H films are Si-rich, the refractive index n has a value close to the c-Si one and then, an additional layer of low-n SiN x :H is deposited in order to improve the internal reflection of photons inside the solar cell. Two splits are done in the batch : 50 % of the wafers are deoxidized by HF dip and two stoichiometries of a-SiC x :H at [C] = 0.15 and [C] = 0.24 are chosen as they are more temperature-stable than the Si-richest stoichiometry. An oxidized wafer is processed as a standard solar cell and is the reference of the batch. The rear dielectric is then opened using UV pulsed laser beam, before complete metallization by Al-screenprinting.

DISCUSSION AND CONCLUSION

The unavailability of the solar cell results does not permit us to conclude neither about the gain obtained by a a-SiC x :H/SiN x :H stack compared to a simple metallization layer nor about the confirmed tendency of the a-SiC x :H passivation observed in Figure 1. Although we don't have any quantitative results, limitations are expected Some problems could occur after the solar cell process which would make the obtained results not optimal. The low stability of a-SiC x :H under high-thermal step as co-firing may cause some blistering of Si-H bonds increasing dangling bonds at the interface with c-Si and then some shunt effect at the electrical contacts. But the back-side SiN x :H could protect the a-SiC x :H and limit its degradation. Lower-thermal process for metallization would then be required to save the passivating properties of a-SiC x :H like aluminium sputtering or aluminium deposition by Physical Vapor Deposition for the rear side of the solar cell after a first firing for the front-side metallization. The Al-Si interface at the opened-laser contacts is also something critical. The diffusion of Si in Al is more rapid than the diffusion of Al in Si during the firing leading the voids formation [10]. Aluminum paste used in the frame of the study could not be optimized for rear-side screenprinted as it can absorb the diffused silicon. The fillfactor could then be affected by a loss of conductivity at the localised contacts. In order to limit the formation of voids, we could apply a cooling-down of the temperature after the firing process facilitating the Al-Si alloy.

Figure 1 :

 1 Figure 1: Surface recombination velocity before and after rapid thermal annealing at 500 °C for 3 stoichiometries

Figure 2 :

 2 C(V) curves at 1 kHz obtained on p-type (a) and n-type (b) c-Si substrate for [C] = 0.15, [C] = 0.24 and [C] = 0.37.

Figure 2

 2 Figure 2 displays the experimental C(V) fitted by the Nicollian & Brews model. The amphoteric nature of the fixed charge (explained in ref. [8]) is demonstrated by comparing the change of the sign of the flat-band voltage: negative in case of n-type c-Si substrate and positive in case of p-type c-Si substrate. Moreover, at a gate voltage of 0 mV or around 670 mV (ellipses on Figure 2) which is an usual open-circuit voltage of a PERC solar cell, the a-SiC x :H/c-Si interface is under accumulation regime.With local aluminum contacts, we would have an extended BSF to the whole rear face. This result is thus an argument for using a-SiC x :H as a rear-side passivation layer.

Figure 3 :Figure 4 :

 34 Figure 3: Process flow followed for PERC solar cellsThe final schemes of PERC solar cells are illustrated on Figure4afor a solar cell without front oxide layer and on Figure4bfor a solar cell with front oxide layer.

Table I :

 I Experimental parameters of deposition

	Temperature	370 °C
	Pressure	1500 mTorr
	Peak-power of plasma	0.3 W.cm -2
	Effective power of plasma	0.052 W.cm -2

Acknowledgments :

I would like to acknowledge Nanolyon Platform team who took a certain part in this work. Funding is provided by a grant from Région Rhône-Alpes (France).

REFERENCES: