Simultaneous Embeddings with Few Bends and CrossingsFrati, Fabrizio and Hoffmann, Michael and Kusters, Vincent (2015) Simultaneous Embeddings with Few Bends and Crossings. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 2426, 2015 , pp. 166179(Official URL: http://dx.doi.org/10.1007/9783319272610_14). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319272610_14
AbstractA 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 their common vertices and edges. 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. This improves on results by Grilli et al. (GD’14), who prove that nine bends per edge suffice, and by Chan et al. (GD’14), who prove that twentyfour crossings per edge pair suffice.
Actions (login required)
