Drawing Partially Embedded and Simultaneously Planar Graphs

Chan, Timothy M. and Frati, Fabrizio and Gutwenger, Carsten and Lubiw, Anna and Mutzel, Petra and Schaefer, Marcus (2014) Drawing Partially Embedded and Simultaneously Planar Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 25-39(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_3).

Full text not available from this repository.


We investigate the problem of constructing planar drawings with few bends for two related problems, the partially embedded graph (PEG) problem—to extend a straight-line planar drawing of a subgraph to a planar drawing of the whole graph—and the simultaneous planarity (SEFE) problem—to find planar drawings of two graphs that coincide on shared vertices and edges. In both cases we show that if the required planar drawings exist, then there are planar drawings with a linear number of bends per edge and, in the case of simultaneous planarity, a constant number of crossings between every pair of edges. Our proofs provide efficient algorithms if the combinatorial embedding information about the drawing is given. Our result on partially embedded graph drawing generalizes a classic result of Pach and Wenger showing that any planar graph can be drawn with fixed locations for its vertices and with a linear number of bends per edge.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_3
Classifications: G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1419

Actions (login required)

View Item View Item