Проблема проверки графа на планарность (можно ли нарисовать его на плоскости без пересечения ребер) имеет важнейшее значение в проектировании топологии печатных плат и микрочипов (VLSI). Теорема Куратовского дает точный критерий (отсутствие подграфов K5 и K3,3), но наивный поиск этих подструктур занимает катастрофическое время O(V^6). В 1974 году Джон Хопкрофт и Роберт Тарьян совершили алгоритмическую революцию, создав алгоритм проверки, работающий за абсолютно линейное время O(V).

Обычные бинарные деревья поиска обладают отличным временем операций O(log N), но только если данные поступают в случайном порядке. Если загрузить в дерево уже отсортированный массив, оно выродится в длинную "макаронину", и время поиска деградирует до O(N). Строгие балансировщики (АВЛ-деревья или Красно-черные деревья) решают проблему, но их реализация требует сотен строк сложного кода с вращениями. Дискретная математика предлагает невероятно элегантную альтернативу — рандомизированное Декартово дерево (Treap).

При решении задач о поиске максимального потока в транспортных сетях классический алгоритм Форда-Фалкерсона имеет фатальный недостаток: его время работы зависит от величины самого потока. Если пропускные способности ребер иррациональны, алгоритм может вообще никогда не завершиться. Эту проблему блестяще решил советский математик Ефим Диниц в 1970 году, предложив алгоритм, работающий за строго полиномиальное время, не зависящее от значений пропускных способностей.