$K$-планарные графы

Граф называется $k$-планарным, если его можно так изобразить на плоскости, что каждое ребро пересекает не более чем $k$ других. Наверное, впервые появилось такое обобщение планарных графов в работе Рингеля в 1965 году — там были рассмотрены 1-планарные графы и доказано, что любой такой граф имеет правильную раскраску вершин в 7 цветов. Позже были определены $k$-планарные графы для всех натуральных $k$. В работах Рингеля, Паха, Тота, Оре, Бородина и других исследовались вопросы об оценке на количество ребер в таких графах, оценке хроматического числа, различные вопросы об их изображениях на плоскости. В докладе будет рассказано о классических и современных результатах из этой области.