Самый большой общий подграф двух максимальных плоских графов

Рассмотрим следующую проблему -

С учетом максимальной плоских графов и G 2 , найти граф с максимальным числом ребер таким образом, что существует подграф (не обязательно индуцируется) в обоих и , изоморфная .$G_1$$G_2$$G$$G_1$$G_2$$G$

Можно ли это сделать за полиномиальное время? Если да, то как?

Известно, что если и являются общими графами, то проблема является NP-полной (потому что может быть кликой). Также известно, что если и являются деревьями или частичными k-деревьями ограниченной степени, то проблема может быть решена за полиномиальное время. Так что насчет максимального плоского случая? Кто-нибудь знает это? Изоморфизм графов на двух максимальных плоских графах является полиномиальным. Возможно, это как-то помогает?$G_1$$G_2$$G_1$$G_1$$G_2$

Он NP-полон, через модифицированную версию редукции, которую Вигдерсон использовал для доказательства того, что гамильтоновость максимальных плоских графов NP-полна.

Тщательное изучение NP-полноты доказательства твердости Вигдерсона в 1982 году для гамильтоновых циклов в максимальных плоских графах ( http://www.math.ias.edu/avi/node/820 ) показывает, что экземпляры, полученные в результате его редукции, обладают свойством существует ребро такое, что либо существует гамильтонов цикл через e, либо вообще не существует гамильтонов цикла. Например, e можно выбрать как один из ребер в одном из M- гаджетов Вигдерсона.$e$$e$$e$$M$

$G$$G$$e$$e$$G$$c$$H$$n$$G$

$(H,B)$$B$$H$$c$$H$$c$$2c$$H$

$G$$e$$G$$c(n+2)$$c(n-1)$$3c$$G$$c$$3c$$c(n-1)$$H$$B$$c(n+2)$