Christophe Weibel

  1. Congestion in planar graphs with demands on faces.

    Authors: Guyslain Naves, Christophe Weibel
    Subjects: Discrete Mathematics
    Abstract

    We give an algorithm to route a multicommodity flow in a planar graph $G$
    with congestion $O(\log k)$, where $k$ is the maximum number of terminals on
    the boundary of a face, when each demand edge lie on a face of $G$. We also
    show that our specific method cannot achieve a substantially better congestion.

  2. Maximal f-vectors of Minkowski sums of large numbers of polytopes.

    Authors: Christophe Weibel
    Subjects: Computational Geometry
    Abstract

    It is known that in the Minkowski sum of $r$ polytopes in dimension $d$, with
    $r<d$, the number of vertices of the sum can potentially be as high as the
    product of the number of vertices in each summand. However, the number of
    vertices for sums of more polytopes was unknown so far.

Syndicate content