A Simple Linear-Time Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its Applications

Authors Tatsuya Akutsu, Colin de la Higuera, Takeyuki Tamura



PDF
Thumbnail PDF

File

LIPIcs.CPM.2018.10.pdf
  • Filesize: 475 kB
  • 12 pages

Document Identifiers

Author Details

Tatsuya Akutsu
  • Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan
Colin de la Higuera
  • LINA, UMR CNRS 6241, Universitéde Nantes, 44322 Nantes Cedex 03, France
Takeyuki Tamura
  • Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan

Cite AsGet BibTex

Tatsuya Akutsu, Colin de la Higuera, and Takeyuki Tamura. A Simple Linear-Time Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its Applications. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CPM.2018.10

Abstract

We present a simple linear-time algorithm for computing the topological centroid and the canonical form of a plane graph. Although the targets are restricted to plane graphs, it is much simpler than the linear-time algorithm by Hopcroft and Wong for determination of the canonical form and isomorphism of planar graphs. By utilizing a modified centroid for outerplanar graphs, we present a linear-time algorithm for a geometric version of the maximum common connected edge subgraph (MCCES) problem for the special case in which input geometric graphs have outerplanar structures, MCCES can be obtained by deleting at most a constant number of edges from each input graph, and both the maximum degree and the maximum face degree are bounded by constants.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Plane graph
  • Graph isomorphism
  • Maximum common subgraph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Faisal N. Abu-Khzam. Maximum common induced subgraph parameterized by vertex cover. Inf. Process. Lett., 114(3):99-103, 2014. URL: http://dx.doi.org/10.1016/j.ipl.2013.11.007.
  2. Tatsuya Akutsu. A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. IEICE Transactions, 76-A(9):1488-1493, 1993. Google Scholar
  3. Tatsuya Akutsu. A bisection algorithm for grammar-based compression of ordered trees. Inf. Process. Lett., 110(18-19):815-820, 2010. URL: http://dx.doi.org/10.1016/j.ipl.2010.07.004.
  4. Tatsuya Akutsu and Takeyuki Tamura. On the complexity of the maximum common subgraph problem for partial k-trees of bounded degree. In Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee, editors, Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings, volume 7676 of Lecture Notes in Computer Science, pages 146-155. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-35261-4_18.
  5. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684-697. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897542.
  6. Kellogg S. Booth. Lexicographically least circular substrings. Inf. Process. Lett., 10(4/5):240-242, 1980. URL: http://dx.doi.org/10.1016/0020-0190(80)90149-0.
  7. Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph matching in pattern recognition. IJPRAI, 18(3):265-298, 2004. URL: http://dx.doi.org/10.1142/S0218001404003228.
  8. Andreas Fischer, Kaspar Riesen, and Horst Bunke. Improved quadratic time approximation of graph edit distance by combining hausdorff matching and greedy assignment. Pattern Recognition Letters, 87:55-62, 2017. URL: http://dx.doi.org/10.1016/j.patrec.2016.06.014.
  9. Moses Ganardi, Danny Hucke, Markus Lohrey, and Eric Noeth. Tree compression using string grammars. Algorithmica, 80(3):885-917, 2018. URL: http://dx.doi.org/10.1007/s00453-017-0279-3.
  10. John E. Hopcroft and Robert Endre Tarjan. A V log V algorithm for isomorphism of triconnected planar graphs. J. Comput. Syst. Sci., 7(3):323-331, 1973. URL: http://dx.doi.org/10.1016/S0022-0000(73)80013-3.
  11. John E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Robert L. Constable, Robert W. Ritchie, Jack W. Carlyle, and Michael A. Harrison, editors, Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1974, Seattle, Washington, USA, pages 172-184. ACM, 1974. URL: http://dx.doi.org/10.1145/800119.803896.
  12. Costas S. Iliopoulos and William F. Smyth. Optimal algorithms for computing the canonical form of a circular string. Theor. Comput. Sci., 92(1):87-105, 1992. URL: http://dx.doi.org/10.1016/0304-3975(92)90137-5.
  13. Nils Kriege, Florian Kurpicz, and Petra Mutzel. On maximum common subgraph problems in series-parallel graphs. Eur. J. Comb., 68:79-95, 2018. URL: http://dx.doi.org/10.1016/j.ejc.2017.07.012.
  14. Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci., 25(1):42-65, 1982. URL: http://dx.doi.org/10.1016/0022-0000(82)90009-5.
  15. Joseph Manning and Mikhail J. Atallah. Fast detection and display of symmetry in outerplanar graphs. Discrete Applied Mathematics, 39(1):13-35, 1992. URL: http://dx.doi.org/10.1016/0166-218X(92)90112-N.
  16. Jiří Matoušek and Robin Thomas. On the complexity of finding iso- and other morphisms for partial k-trees. Discrete Mathematics, 108(1-3):343-364, 1992. URL: http://dx.doi.org/10.1016/0012-365X(92)90687-B.
  17. Franco P. Preparata and Michael Ian Shamos. Computational Geometry - An Introduction. Texts and Monographs in Computer Science. Springer, 1985. URL: http://dx.doi.org/10.1007/978-1-4612-1098-6.
  18. Christine Solnon, Guillaume Damiand, Colin de la Higuera, and Jean-Christophe Janodet. On the complexity of submap isomorphism and maximum common submap problems. Pattern Recognition, 48(2):302-316, 2015. URL: http://dx.doi.org/10.1016/j.patcog.2014.05.019.
  19. Kokichi Sugihara. An n log n algorithm for determining the congruity of polyhedra. J. Comput. Syst. Sci., 29(1):36-47, 1984. URL: http://dx.doi.org/10.1016/0022-0000(84)90011-4.
  20. KHaim J. Wolfson and Isidore Rigoutsos. Geometric hashing: An overview. IEEE Comput. Sci. &Eng., 4(4):10-21, 1997. URL: http://dx.doi.org/10.1109/99.641604.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail