Simultaneous Embeddings with Few Bends and Crossings
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 the common vertices and edges of R and 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: if R and B are trees then one bend per edge and four crossings per edge pair suffice (and one bend per edge is sometimes necessary), if R is a planar graph and B is a tree then six bends per edge and eight crossings per edge pair suffice, and if R and B are planar graphs then six bends per edge and sixteen crossings per edge pair suffice. 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. (JGAA '15), which proves that twenty-four crossings per edge pair suffice., number=4, journal=Journal of Graph Algorithms and Applications, author=Frati, Fabrizio and Hoffmann, Michael and Kusters, Vincent, year=2019, month=Sep., pages=683–713