Home

Пятница 11 мая, 18-00, ауд. 106

Пятница, 11 мая, ауд. 106. Начало в 18:00.

Докладчик: Глеб Ненашев (СПбГУ).

Тема: Оценка количества рёбер в 3-почти планарном графе.

Abstract

Граф называется k-почти планарным, если его можно изобразить на плоскости так чтобы каждое ребро пересекало не более $ k $ других. Будет доказано, что для 3-почти планарного графа $ G $ верна оценка $ e(G)\leq 5.5v(G) - 11 $. А так же показана серия примеров, когда $ e(G)= 5.5v(G) - 15 $.