- Progress: not really, the case of 2 known blue points + 2 unknown red points in 1d seems easy.

- Coordinator: Jyoti, Nishat. Other people involved: S. Felsner, S. Kobourov, W. Evans, M. Kaufmann, Kevin Verbeek. Fan supporters: Bill Lenhart, Rob Hochberg, Sylvain Lazard, Sue Whitesides
- Progress: nxm tables with convex quadrants. Solution for outer rectangle, convex quadrilateral, (convex?) n-gon n>4, circle with circular arcs inside, sphere.

- Solution for a 2xn table. consider an infinite parallel-axis rectangle of height 2. On the top edge draw segments of length the area of the top row of the table. Similarly, on the botton edge, draw segments of length the area of the bottom row of the table. Connect the vertices, defining trapezoids and triangulate them. This gives a set of triangles whose area are the values in the table. However the top and bottom side have different length (in general). Assuming that sum of the bi (bottom row) is larger or equal than the sum of the ai (top row), consider trapezoids defines by the 4 triangles b_ia_ia_{i+1}{b_{i+1}. The area of this trapezoid is the sum of the area of b_ia_ia_{i+1}{b_{i+1} and it does not change by shrinking the bottom two edges and enlarging the top two edge as long as the sum of the lengths of the four edges does not change. While this trapezoid deforms, the inner cells deform so that their areas do not change. The other trapezoids deform while their top and bottom edge translate but their area remains unchanged. Eventually, the top and bottom sides have the same length which concludes the construction.
- Solution for the nxm rectangle. Split the table in two parts so that the area are the same above and below (possibly cutting a row into 2). In each of the sub-tables sum the values in the columns. This gives a 2xn table. Apply the algorithm for 2xn tables and for each cell, divide it in a simple manner into m/2 regions of the correct area (for instance for a triangle, draw m/2-1 edges from one of the vertices.
- Solution for any atrbitrary polygon: if it is a rectangle, we can do it. If it is an n-gon when n>4, then there isn't always a solution.
- In a circle with circular arcs. It is not always possible to draw the cartogram of the table in a circle with straight lines
- On a sphere with spherical straight lines
- Open problem 1: Find a proof for arbitrary quadrangle using air pressure technique
- Open problem 2: Solve 2x2x2

- Coordinator: Jyoti. Other people involved: Beppe, Bill, Nishat, Zahed.
- Progress. Known: Planar cubic graphs drawable with 4 slopes if allowing crossing and 6 slopes otherwise. Plane 3-tree it is possible with the max-degree^5 sloples, and outerplanar graphs with delta-1 slopes.
- New results. On Halin graphs (a tree where all the leaves are connected in a cycle) with delta+3 slopes.

Rips complex: given a set of points P, consider the proximity graph induced by placing balls of radius alpha at every point. The Rips complex is all the cliques of the proximity graph.

- Coordinator: Dominique Attali. People involved Olivier Devillers, Marc Glisse, Sylvain Lazard. Friend: Ulrike Stege
- Progress: The current idea is to use a contractible modified torus (add two faces to fill the loops and make a hole) whose triangulation has few neat edge contractions. On the variable gadget we have to identify a "true"and a "false" edges that are neat-contractable (but not both at the beginning) and a lock that is neat-contractable and allow the neat-contraction of the second edge. On the clause gadget we need three neat-contractible edges for the litterals and a key that is not neat-contractible until one of the litteral has been contracted.

Planar graphs: m<=3n-6.

RAC (right angle crossings): m<=4n-10.

RAC with one bend per edge: m=O(n^?)

RAC with 2 bends per edges: m=O(n^{7/4})

RAC with 3 bends per edges: Kn and there is a construction that uses O(n^4) area.

RAC with 4 bends per edges: Kn and there is a construction that uses O(n^3) area.

Question: Is this optimal?

Given 2 curves f and g with same endpoints and f above g (where above is to be defined appropriately). Find curves f' and g' with same endpoints and f' below g' such that they minimize the max of the Frechet distances between f and f' and between g and g'. It is not known whether one minimum is realized with f'=g'.

- Coordinator: Carola Wenk. People involved: Helmut Alt, Friends: Sylvain Lazard, Michael Kaufmann, Will Evans, Sue Whitesides
- Progress: Example of two curves where the solution with one curve (f'=g') is distinct from the two curves problems. The problem with one curve seems quite difficult because one actually wants a simple curve f'=g' which makes the problem more complicated.

Givem n point in R3. What is the largest subset C of P in convex position.

Known: NP-hard, W[1]-hard. There always exists a subset C of size Theta(log n)

Problem: approximation algorithm? There exists a Theta(n/log n) approx factor in poly time

G+=G+s and connect s to every ariticulation point.

G+ is planar iff G is bar-visibility graph (a bar-visibility graph is a graph whose vertices can be represented by vertical segments that are connected by edges iff they are horizontaly visibles)

Question: Characterize bar 1-visibility graphs (vertical segments are slightly transparent so that one can see through 1 segment but not through 2 of them). Consider Strong bar 1-visibility graphs: if two segments see each other (possibly trhough another edge), there must be an edge in the corresponding graph.

- Coordinator: Tamara. People involved: Bill Lenhart, Beppe Liotta, Micheal Kaufmann, Will Evans, Steve Wisath Fan supporters: Sue Whitesides, Laurie Heyer.
- Progress. Some remarks
- Strong Bar-1 Visibility: If two bars are either directly (empty rectangle of epsilon-width between the bars) or indirectly (epsilon-width rectangle may intersect a single, third bar) then the edge between the two bars must exist in the graph
- Subclasses based on stabbing bars by vertical lines:
- Maximum of two bars stabbed by any vertical line: This is exactly the class of catepillars. Note that these are the only triangle-free strong bar-1 visibility graphs
- Max. of 3 bars stabbed: These are the "fat caterpillars" in which any leg can be replaced by an "augmented" fan of triangles and any segment of the spine can be replaced by an "augmented" path of triangles. Augmented means that any internal edge can have a set of triangles attached to it.
- Max. of 4 bars is mostly completely characterized: stay tuned

Measure of simplices.

Segment: length/2

triangle: obtuse: measure = 0. Acute : circomscribing radius - max measure of segments

We grow disks around vertices. For acute triangles, at one point the three disks define a hole . We are interested in the life-expectency of that hole (or persistence)

For tetrahedra, if the center of the circomscribing sphere is outside of the tetrahedron we set the measure to 0, otherwise, we take the radius minus max of the measures of its faces.

For n points in 3D on 2 segments so that the Delaunay triangulation has size n^2 its seems that the total persistence is O(1). For points uniformly distributed in a ball, the total persistence (seems to be) n times 1/cubic root of n.

Question: can we bound the total persistence?

- Progress: For the number of connected components, the total persistence is the length of the MST that is bounded by O(n^{1-1/d}). For the cavities, we match a cavity with a certain volume so that the persistence of a cavity can be split in "element of persistence". The sum of "element of persistence"to the power d is then bounded by a constant and we get by Cauchy-Schwartz that the number of cavities is O(n^{\floor{d/2}^(1-1/d)}).
- Coordinator: Marc. People involved: Dominique, Olivier, Sylvain.

Delaunay is known to be a t-spanner in 2D.

For L_2 Delaunay [Xia; SoCG'11], it is known that t<1.98 and there exists counter example that prove that t>Pi/2+0.01

For L_1- and L_infty-Delaunay [Bonichon et. al.; ESA'12], the stretch factor is \sqrt{4+2\sqrt{2}}= 2.61

What about 3D ? Is Delaunay a t-spanner for some constant t ?

- Coordinator: Marc Glisse People involved: Zahed Rahmati, Olivier Devillers, Raimund Seidel, Sylvain Lazard, Dominique Attali. Friend of spanners: Christian Knauer.
- Progress: We got a lower bound that Delaunay cannot be better than a \frac{\pi}{\sqrt{2}} spanner. The example is a suitable quadrilaterization of the sphere with tiles that are close to squares. The factor is obtained as the product of (i) a factor pi/2 for the ration of the length of a half great circle over the diameter of the sphere and (ii) a factor sqrt{2} that corresponds to the zigzags detour that are made along this great circle because of the suitable quadrilaterization of the sphere. Then a perturbation ensure a unique Delaunay triangulation that produce the desired ratio. Using a similar argument, for L_infty, we can get a lower bound of 2.61*sqrt(2), that is 3.6.

From http://www.ics.uci.edu/~eppstein/200-f01.pdf

Given a rectangle partitioned into smaller rectangles. Find a tree touching each rectangle (including outer one). Tree edges must lie along rectangle sides. Minimize total length.

no algorithm known (not even guaranteed approx. ratio). NP-complete?

An NP-complete variant can be found in http://www.cs.berkeley.edu/~smaji/reports/bwp-note.pdf

- People involved: Rob, Ulrike, Helmut Raimund Christian Zahled Sue Carl Laurie Carola
- Can be done
- for a n by n grid of a times b
- brickwall with tiles 1 by 2 (wires of length 1, so length = # wires)
- conjecture : needs # faces - 3 wires (does not work, counter example)
- rectilinear drawing of degree 3, minimum number of wires is # blocks -2
- next step : short total length