Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 08, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Vincent Kusters
A simultaneous embedding with fixed edges (SEFE) of two planar graphs $R$ and $B$ is a pair of plane drawings of $R$ and $B$ that coincide when restricted to $R\cap B$. We show that whenever $R$ and $B$ admit a SEFE, they also admit a SEFE in which every edge is a polygonal curve with few bends and every pair of edges has few crossings. Specifically: (1) if $R$ and $B$ are trees then one bend per edge and four crossings per edge pair suffice, (2) if $R$ is a planar graph and $B$ is a tree then six bends per edge and eight crossings per edge pair suffice, and (3) if $R$ and $B$ are planar graphs then six bends per edge and sixteen crossings per edge pair suffice. The number of bends in (1) is tight. Our results simultaneously improve on a paper by Grilli et al. (GD'14), which proves that nine bends per edge suffice, and on a paper by Chan et al. (GD'14), which proves that twenty-four crossings per edge pair suffice.
Joint work with Fabrizio Frati and Michael Hoffmann.
Automatic MiSe System Software Version 1.4803M | admin login