Simultaneous Embedding of Planar Graphs with Few Bends

Erten, Cesim and Kobourov, Stephen G. (2004) Simultaneous Embedding of Planar Graphs with Few Bends. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 195-205(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_21).

Full text not available from this repository.

Abstract

We present an O(n) time algorithm for simultaneous embedding of pairs of planar graphs on the O(n^2)× O(n^2) grid, with at most three bends per edge, where n is the number of vertices. For the case when the input graphs are both trees, only one bend per edge is required. We also describe an O(n) time algorithm for simultaneous embedding with fixed-edges for tree-path pairs on the O(n)× O(n^2) grid with at most one bend per tree-edge and no bends along path edges. This work is partially supported by the NSF under grant ACR-0222920 and by ITCDI under grant 003297.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_21
Classifications: M Methods > M.900 Tree
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.210 Bends
URI: http://gdea.informatik.uni-koeln.de/id/eprint/587

Actions (login required)

View Item View Item