Аннотация:Медведеву А.Д. удалось показать, что гамма-алгоритм (алгоритм плоской укладки планарных графов) не применим в явном виде для укладки бипланарных графов (t(G)=2). Далее Андрей исследовал как связано число ребер, одной из планарных долей бипланарного графа с количеством вершин и ребер исходного графа. Ему удалось доказать тривиальные оценки на мощность множества ребер.
Так как в общем виде задача определения бипланарности графов является NP-полной, то ожидать полиномиального алгоритма укладки бипланарных графов не приходится. Однако могут существовать большие семейства графов, допускающие простую укладку. Медведевым А.Д. было найдено несколько таких семейств и доказана полиномиальность алгоритмов их укладки.