Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Twenty-second International Symposium on Graph Drawing, GD 2014
DOI: 10.7155/jgaa.00375
Drawing Partially Embedded and Simultaneously Planar Graphs
Vol. 19, no. 2, pp. 681-706, 2015. Regular paper.
Abstract We investigate the problem of constructing planar drawings with few bends for two related problems, the partially embedded graph problem-to extend a straight-line planar drawing of a subgraph to a planar drawing of the whole graph-and the simultaneous planarity 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, with a number of crossings between any pair of edges which is bounded by a constant. Our proofs provide efficient algorithms if the combinatorial embedding of the drawing is given. Our result on partially embedded graph drawing generalizes a classic result by Pach and Wenger which shows that any planar graph can be drawn with a linear number of bends per edge if the location of each vertex is fixed.
Submitted: October 2014.
Reviewed: August 2015.
Revised: September 2015.
Accepted: October 2015.
Final: October 2015.
Published: November 2015.
Communicated by Christian Duncan and Antonios Symvonis
article (PDF)
BibTeX