×

A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications. (English) Zbl 1497.68361

Navarro, Gonzalo (ed.) et al., 29th annual symposium on combinatorial pattern matching, CPM 2018, July 2–4, 2018, Qingdao, China. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 105, Article 10, 12 p. (2018).
Summary: 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.
For the entire collection see [Zbl 1390.68025].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Faisal N. Abu-Khzam. Maximum common induced subgraph parameterized by vertex cover. {\it Inf. Process. Lett.}, 114(3):99-103, 2014. doi:10.1016/j.ipl.2013.11.007. · Zbl 1284.68274
[2] Tatsuya Akutsu. A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. {\it IEICE Transactions}, 76-A(9):1488-1493, 1993.
[3] Tatsuya Akutsu. A bisection algorithm for grammar-based compression of ordered trees. {\it Inf. Process. Lett.}, 110(18-19):815-820, 2010. doi:10.1016/j.ipl.2010.07.004. · Zbl 1234.68099
[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, {\it Algorithms and Computation - 23rd International Sym-} {\it posium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings}, volume 7676 of {\it Lecture Notes in Computer Science}, pages 146-155. Springer, 2012.doi:10.1007/ 978-3-642-35261-4_18. · Zbl 1260.68169
[5] László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, {\it Proceedings of the 48th Annual ACM SIGACT Sym-} {\it posium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016}, pages 684-697. ACM, 2016. doi:10.1145/2897518.2897542. · Zbl 1376.68058
[6] Kellogg S. Booth.Lexicographically least circular substrings.{\it Inf. Process. Lett.}, 10(4/5):240-242, 1980. doi:10.1016/0020-0190(80)90149-0. · Zbl 0444.68064
[7] Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento.Thirty years of graph matching in pattern recognition.{\it IJPRAI}, 18(3):265-298, 2004.doi: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. {\it Pattern} {\it Recognition Letters}, 87:55-62, 2017. doi:10.1016/j.patrec.2016.06.014.
[9] Moses Ganardi, Danny Hucke, Markus Lohrey, and Eric Noeth. Tree compression using string grammars. {\it Algorithmica}, 80(3):885-917, 2018. doi:10.1007/s00453-017-0279-3. · Zbl 1384.68016
[10] :11
[11] John E. Hopcroft and Robert Endre Tarjan. A V log V algorithm for isomorphism of triconnected planar graphs. {\it J. Comput. Syst. Sci.}, 7(3):323-331, 1973. doi:10.1016/ S0022-0000(73)80013-3. · Zbl 0274.05103
[12] :12
[13] 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, {\it Proceedings of the 6th Annual ACM Symposium on Theory} {\it of Computing, April 30 - May 2, 1974, Seattle, Washington, USA}, pages 172-184. ACM, 1974. doi:10.1145/800119.803896. · Zbl 0369.05028
[14] Costas S. Iliopoulos and William F. Smyth.Optimal algorithms for computing the canonical form of a circular string.{\it Theor. Comput. Sci.}, 92(1):87-105, 1992.doi: 10.1016/0304-3975(92)90137-5. · Zbl 0747.68029
[15] Nils Kriege, Florian Kurpicz, and Petra Mutzel. On maximum common subgraph problems in series-parallel graphs. {\it Eur. J. Comb.}, 68:79-95, 2018. doi:10.1016/j.ejc.2017.07. 012. · Zbl 1373.05120
[16] Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. {\it J. Comput. Syst. Sci.}, 25(1):42-65, 1982. doi:10.1016/0022-0000(82)90009-5. · Zbl 0493.68064
[17] Joseph Manning and Mikhail J. Atallah.Fast detection and display of symmetry in outerplanar graphs.{\it Discrete Applied Mathematics}, 39(1):13-35, 1992.doi:10.1016/ 0166-218X(92)90112-N. · Zbl 0768.68165
[18] Jiří Matoušek and Robin Thomas. On the complexity of finding iso- and other morphisms for partial k-trees. {\it Discrete Mathematics}, 108(1-3):343-364, 1992. doi:10.1016/ 0012-365X(92)90687-B. · Zbl 0764.68128
[19] Franco P. Preparata and Michael Ian Shamos.{\it Computational Geometry - An Intro-} {\it duction}.Texts and Monographs in Computer Science. Springer, 1985.doi:10.1007/ 978-1-4612-1098-6. · Zbl 0759.68037
[20] Christine Solnon, Guillaume Damiand, Colin de la Higuera, and Jean-Christophe Janodet. On the complexity of submap isomorphism and maximum common submap problems. {\it Pattern Recognition}, 48(2):302-316, 2015. doi:10.1016/j.patcog.2014.05.019. · Zbl 1373.68355
[21] Kokichi Sugihara. An n log n algorithm for determining the congruity of polyhedra. {\it J.} {\it Comput. Syst. Sci.}, 29(1):36-47, 1984. doi:10.1016/0022-0000(84)90011-4. · Zbl 0546.68052
[22] KHaim J. Wolfson and Isidore Rigoutsos. Geometric hashing: An overview. {\it IEEE Comput.} {\it Sci. & Eng.}, 4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.