ENS Lyon, November 2014

1. Dynamic programing algorithm for isopermetric problems in graphs of bounded treewidth

A dynamic programing algorithm to compute the vertex isoperimetric function for trees has been proposed by Kratochvil and Serra. The object of the project is to design a similar algorithm for the edge case and its implementation to graphs of bounded treewidth.

Contact: Oriol Serra, C3-113, Campus Nord UPC, Thursday Nov 27, 17h30

2. Deflection routing in De Bruijn and Kautz networks

Routing in bufferless networks can be performed without packet loss by deflecting packets when links are not available. The efficiency of this kind of protocol, known as deflection routing, is highly determined by both the network topology and the decision rule used to choose which packets have to be deflected when a conflict arises (i.e. when multiple packets contend for a single outgoing link). The object of the project is to develop analytical methods to compute the maximum load that nodes can offer to the network under different deflection criteria. If the network topologies under consideration correspond to
De Bruijn and Kautz digraphs or, more generally, to some families of iterated line digraphs, a careful study of the vertex layer
structure of such digraphs can be performed that allow us to formulate explicit expressions for the deflection probabilities.

Contact: Josep Fàbrega, C3-112, Campus Nord UPC, Thursday Nov 27, 17h30

3. The degree/diameter problem in maximal planar graphs

We consider simple maximal planar graphs G = G(V,E). A graph is simple if it doesn’t have loops or multiple edges. If a graph can be drawn on the plane without any crossing of its edges, then the graph is called planar. A planar graph is maximal if when we add a new edge, the graph obtained is no longer planar. A maximal planar graph divides the plane into triangles.

The (∆, D) problem consists of finding the maximum number of vertices n = |V | among all the possible graphs G with maximum degree ∆ and diameter D. This is a prominent topic in graph theory, with results obtained for many cases. Information about this problem, for graphs in general, can be found in the survey by Miller and Siran, and for planar graphs also on the web page by Loz, Pérez-Rosés, and Pineda-Villavicencio.

For simple maximal planar graphs (that is, triangulations), the (∆, D) problem with diameter D = 2 and ∆ ≥ 8 was solved by Seyffarth. For simple planar graphs, Fellows, Hell and Seyffarth found an upper bound on the number of vertices. In this project, we intend to find a better upper bound for simple maximal planar graphs with diameter D > 2.

Advisors: Cristina Dalfó and Clemens Huemer, Universitat Politècnica de Catalunya, BarcelonaTech Dept. de Matemàtica Aplicada IV {cristina.dalfo,clemens.huemer}@upc.edu

Contact:  C3-107, Campus Nord UPC, Thursday Nov 27, 17h30