Disconnectivity and Relative Positions in Simultaneous Embeddings

Bläsius, Thomas and Rutter, Ignaz (2013) Disconnectivity and Relative Positions in Simultaneous Embeddings. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 31-42 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_4).

Full text not available from this repository.


For two planar graph $G^{\textcircled1}$ = ($V^{\textcircled1}$, $E^{\textcircled1}$) and $G^{\textcircled2}$ = ($V^{\textcircled2}$, $E^{\textcircled2}$) sharing a common subgraph G = $G^{\textcircled1}$ ∩ $G^{\textcircled2}$ the problem Simultaneous Embedding with Fixed Edges (SEFE) asks whether they admit planar drawings such that the common graph is drawn the same. Previous algorithms only work for cases where G is connected, and hence do not need to handle relative positions of connected components. We consider the problem where G, $G^{\textcircled1}$ and $G^{\textcircled2}$ are not necessarily connected. First, we show that a general instance of SEFE can be reduced in linear time to an equivalent instance where $V^{\textcircled1}$ = $V^{\textcircled2}$ and $G^{\textcircled1}$ and $G^{\textcircled2}$ are connected. Second, for the case where G consists of disjoint cycles, we introduce the CC-tree which represents all embeddings of G that extend to planar embeddings of $G^{\textcircled1}$. We show that CC-trees can be computed in linear time, and that their intersection is again a CC-tree. This yields a linear-time algorithm for SEFE if all k input graphs (possibly k>2) pairwise share the same set of disjoint cycles. These results, including the CC-tree, extend to the case where G consists of arbitrary connected components, each with a fixed embedding. Then the running time is O(n^2).

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_4
Classifications:G Algorithms and Complexity > G.490 Embeddings
ID Code:1295

Repository Staff Only: item control page


Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 202–221. SIAM (2010)

Angelini, P., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Testing the Simultaneous Embeddability of two Graphs whose Intersection is a Biconnected or a Connected Graph. J. Discr. Alg. 14, 150–172 (2012), http://dx.doi.org/10.1016/j.jda.2011.12.015

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. CoRR abs/1204.5853 (2012)

Bläsius, T., Rutter, I.: Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems. CoRR abs/1112.0245 (2011)

Di Battista, G., Tamassia, R.: On-Line Maintenance of Triconnected Components with SPQR-Trees. Algorithmica 15(4), 302–318 (1996)

Di Battista, G., Tamassia, R.: On-Line Planarity Testing. SIAM J. Comput. 25(5), 956–997 (1996)

Fowler, J.J., Gutwenger, C., Jünger, M., Mutzel, P., Schulz, M.: An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 157–168. Springer, Heidelberg (2009)

Gassner, E., Jünger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous Graph Embeddings with Fixed Edges. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 325–335. Springer, Heidelberg (2006)

Gutwenger, C., Mutzel, P.: A Linear Time Implementation of SPQR-Trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001)

Haeupler, B., Jampani, K.R., Lubiw, A.: Testing Simultaneous Planarity When the Common Graph Is 2-Connected. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol. 6507, pp. 410–421. Springer, Heidelberg (2010)

Jünger, M., Schulz, M.: Intersection Graphs in Simultaneous Embedding with Fixed Edges. Journal of Graph Algorithms and Applications 13(2), 205–218 (2009)

Whitney, H.: Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics 54(1), 150–168 (1932)