Simultaneous Embeddings with Few Bends and Crossings

Frati, 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 24-26, 2015 , pp. 166-179(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_14).

Full text not available from this repository.

Abstract

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 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 twenty-four crossings per edge pair suffice.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:14
Last Modified: 04 May 2016 16:14
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1486

Actions (login required)

View Item View Item