Algorithm for finding one of the largest common subgraphs of two three-dimensional graph structures
Sumio Masuda, Hiroyuki Yoshioka, Eiichi Tanaka · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1998
Given two connected graphs Ga = (Va, Ea) and Gb = (Vb, Eb) with three-dimensional structures. Let na = |Va|, ma = |Ea|, nb = |Vb|, and mb = |Eb|. Let the maximum order of a vertex in Ga(Gb) be la(lb). Initially this paper offers a method to find a largest common subgraph of Ga and Gb in O(lam2albmblognb) time. Then, an algorithm with O(n1.5anblognalognb) time is proposed for the case where Ga is a planar structure with a three-dimensional structure and satisfies the following two conditions. Condition 1: In Ga and Gb, no vertex has order exceeding a specified constant c. Condition 2: In Ga, no two adjacent edges are located on the same straight-line. In particular, we show that when Ga is a tree, and conditions 1 and 2 are satisfied, a largest common substructure of Ga and Gb can be found in O(nanblognalognb) time. © 1998 Scripta Technica, Electron Comm Jpn Pt 3, 81(9): 48–53, 1998