This preprint was accepted March 13, 2007
ABSTRACT:
В работе изучается вопрос о максимальном количестве ребер в $k$-почти планарном графе (то есть графе, который можно нормально изобразить на плоскости так, чтобы каждое ребро пересекалось не более, чем с $k$ другими).
Для случаев $k=1$ и $k=2$ доказано, что количество ребер в $k$-почти планарном графе на $v$ вершинах не
превосходит $(k+3)(v-2)$, построены серии примеров, показывающих точность оценок. Доказывается, что для больших $k$ оценка имеет вид $С_k\sqrt{k} v$ (где $C_k$ --- некоторая константа).
[Full text:
(.ps.gz)]