Drawing Simultaneously Embedded Graphs with Few Bends

Grilli, Luca and Hong, Seok-Hee and Kratochvíl, Jan and Rutter, Ignaz (2014) Drawing Simultaneously Embedded Graphs with Few Bends. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 40-51(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_4).

Full text not available from this repository.


We study the problem of drawing simultaneously embedded graphs with few bends. We show that for any simultaneous embedding with fixed edges (Sefe) of two graphs, there exists a corresponding drawing realizing this embedding such that common edges are drawn as straight-line segments and each exclusive edge has a constant number of bends. If the common graph is biconnected and induced, a straight-line drawing exists. This yields the first efficient testing algorithm for simultaneous geometric embedding (Sge) for a non-trivial class of graphs.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_4
Classifications: G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.540 Planar
P Styles > P.720 Straight-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1420

Actions (login required)

View Item View Item