Topological Morphing of Planar Graphs

Angelini, Patrizio and Cortese, Pier Francesco and Di Battista, Giuseppe and Patrignani, Maurizio (2009) Topological Morphing of Planar Graphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 145-156 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_15).

Full text not available from this repository.

Abstract

In this paper we study how two planar embeddings of the same biconnected graph can be morphed one into the other while minimizing the number of elementary changes.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_15
Classifications:M Methods > M.600 Planar
G Algorithms and Complexity > G.490 Embeddings
ID Code:904

Repository Staff Only: item control page

References

Angelini, P., Cortese, P.F., Di Battista, G., Patrignani, M.: Topological morphing of planar graphs. Tech. Report RT-DIA-134-2008, Dept. of Computer Sci., Univ. di Roma Tre (2008)

Auyeung, A., Abraham, A.: Estimating genome reversal distance by genetic algorithm. CoRR cs.AI/0405014 (2004)

Bachmaier, C.,Brandenburg, F.J., Forster, M.: Track planarity testing and embedding. In: Van Emde Boas, P., Pokorny, J., Bielikova, M., Stuller, J. (eds.) Proc. SOFSEM 2004. vol. 2, pp. 3–17. MatFyzPress (2004)

Bader, D.A., Moret, B.M.E., Yan, M.: A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. Journal of Computational Biology 8(5), 483–491 (2001)

Bertolazzi, P., Di Battista, G., Didimo, W.: Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers 49:8, 826–840 (2000)

Biedl, T.C., Lubiw, A., Spriggs, M.J.: Morphing planar graphs while preserving edge directions. In: Healy, P., Nikolov, N.S. (eds.) Graph Drawing, (GD’05). LNCS, vol. 3843, pp. 13–24. Springer (2005)

Cairns, S.S.: Deformations of plane rectilinear complexes. American Math. Monthly 51, 247–252 (1944)

Caprara, A.: Sorting by reversals is difficult. In: RECOMB 1997: Proceedings of the first annual international conference on Computational molecular biology. pp. 75–83. ACM, New York, NY, USA (1997)

de Fraysseix, H., Ossona de Mendez, P.: P.I.G.A.L.E - Public Implementation of a Graph Algorithm Library and Editor, sourceForge project page http://sourceforge.net/projects/pigale

Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25, 956–997 (1996)

Erten, C., Kobourov, S.G., Pitta, C.: Intersection-free morphing of planar graphs. In: 11th Symposium on Graph Drawing. pp. 320–331 (2003)

Floater, M., Gotsman, C.: How to morph tilings injectively. Journal of Computational and Applied Mathematics 101, 117–129 (1999)

Gotsman, C., Surazhsky, V.: Guaranteed intersection-free polygon morphing. Computers and Graphics 25, 67–75 (2001)

Kaplan, H., Shamir, R., Tarjan, R.E.: Faster and simpler algorithm for sorting signed permutations by reversals. In: SODA ’97. pp. 344–351 (1997)

Lubiw, A., Petrick, M., Spriggs, M.: Morphing orthogonal planar graph drawings. In: SODA ’06. pp. 222–230. ACM (2006)

Meidanis, J., Walter, M., Dias, Z.: Reversal distance of sorting circular chromosomes. Tech. Report IC-00-23, Institute of Computing, Universidade Estadual de Campinas (2000)

Solomon, A., Sutcliffe, P., Lister, R.: Sorting circular permutations by reversal. In: WADS’03. pp. 319–328. Ottawa, Ontario, Canada (2003)

Tannier, E., Bergeron, A., Sagot, M.F.: Advances on sorting by reversals. Discrete Appl. Math. 155(6-7), 881–888 (2007)

Thomassen, C.: Deformations of plane graphs. Journal of Combinatorial Theory, Series B 34, 244–257 (1983)