14:00
15:00

(Uniquement en présentiel / Only offline, no online version)

A geometric graph G is a graph drawn in the Euclidean plane such that its vertices are points in general position and its edges are drawn as straight line segments. Given a complete geometric graph H_n on n vertices, we are interested in finding a large collection of plane copies of a graph G in H_n such that each edge of H_n appears in at most one copy of G. We say a graph G is geometric-packable if for every sequence of geometric complete graphs $(H_n)_{n \geq 1}$ all but o(n^2) edges of H_n can be packed by plane copies of G. In a joint work with Daniel W. Cranston, Jiaxi Nie and Jacques Verstraete, we study geometric-packability and show that if G is a triangle, plane 4-cycle or plane 4-cycle with a chord, the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions).

[Alexandra Wesolek] (Simon Fraser University, Canada)

http://www.sfu.ca/~agwesole/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI (178)