Abstract
Two planar graphs G 1 and G 2 sharing some vertices and edges are simultaneously planar if they have planar drawings such that a shared vertex [edge] is represented by the same point [curve] in both drawings. It is an open problem whether simultaneous planarity can be tested efficiently. We give a linear-time algorithm to test simultaneous planarity when the two graphs share a 2-connected subgraph. Our algorithm extends to the case of k planar graphs where each vertex [edge] is either common to all graphs or belongs to exactly one of them.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Angelini, P., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Testing the simultaneous embeddability of two graphs whose intersection is a biconnected graph or a tree. In: IWOCA. LNCS (2010)
Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with no geometric simultaneous embedding. In: CoRR, abs/1001.0555 (2010)
Booth, K.: PQ Tree Algorithms. PhD thesis, University of California, Berkeley (1975)
Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences 13, 335–379 (1976)
Boyer, J., Myrvold, W.: On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms and Applications 8(3), 241–273 (2004)
Brass, P., Cenek, E., Duncan, C., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.: On simultaneous planar graph embeddings. Computational Geometry: Theory and Applications 36(2), 117–130 (2007)
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley Interscience, Hoboken (1997)
DiGiacomo, G., Liotta, G.: Simultaneous embedding of outerplanar graphs, paths, and cycles. International Journal of Computational Geometry and Applications 17(2), 139–160 (2007)
Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few bends. Journal of Graph Algorithms and Applications 9(3), 347–364 (2005)
Estrella-Balderrama, A., Gassner, E., Junger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous geometric graph embeddings. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 280–290. Springer, Heidelberg (2008)
Even, S., Tarjan, R.: Computing an st-Numbering. Theor. Comput. Sci. 2(3), 339–344 (1976)
Fowler, J., Gutwenger, C., Junger, 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. 1–12. Springer, Heidelberg (2009)
Fowler, J., Jünger, M., Kobourov, S.G., Schulz, M.: Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 146–158. Springer, Heidelberg (2008)
Frati, F.: Embedding graphs simultaneously with fixed edges. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 108–113. Springer, Heidelberg (2007)
Gassner, E., Junger, 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)
Haeupler, B., Jampani, K.R., Lubiw, A.: Testing simultaneous planarity when the common graph is 2-connected (2010)
Haeupler, B., Tarjan, R.E.: Planarity algorithms via PQ-trees (extended abstract). Electronic Notes in Discrete Mathematics 31, 143–149 (2008)
Jampani, K.R., Lubiw, A.: The simultaneous representation problem for chordal, comparability and permutation graphs. In: WADS. LNCS, vol. 5664, pp. 387–398. Springer, Heidelberg (2009)
Jampani, K.R., Lubiw, A.: Simultaneous interval graphs (2010) (submitted)
Jünger, M., Leipert, S.: Level planar embedding in linear time. J. Graph Algorithms Appl. 6(1), 67–113 (2002)
Jünger, M., Schulz, M.: Intersection graphs in simultaneous embedding with fixed edges. Journal of Graph Algorithms and Applications 13(2), 205–218 (2009)
Lempel, A., Even, S., Cederbaum, I.: An algorithm for planarity testing of graphs. In: Rosenstiehl, P. (ed.) Theory of Graphs: International Symposium, pp. 215–232 (1967)
Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)
Nishizeki, T., Chiba, N.: Planar graphs: theory and algorithms. Elsevier, Amsterdam (1988)
Nishizeki, T., Rahman, M.S.: Planar graph drawing. World Scientific, Singapore (2004)
Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics 17(4), 717–728 (2001)
Shih, W.K., Hsu, W.-L.: A new planarity test. Theoretical Computer Science 223(1-2), 179–191 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Haeupler, B., Jampani, K.R., Lubiw, A. (2010). Testing Simultaneous Planarity When the Common Graph Is 2-Connected. In: Cheong, O., Chwa, KY., Park, K. (eds) Algorithms and Computation. ISAAC 2010. Lecture Notes in Computer Science, vol 6507. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17514-5_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-17514-5_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17513-8
Online ISBN: 978-3-642-17514-5
eBook Packages: Computer ScienceComputer Science (R0)