Распределение соединений по слоям. Граф пересечений

Этапы трассировки многослойных печатных плат:
1. [Что?] Для каждой цепи (подмножества эквипотенциальных контактов) определяется порядок соединения этих контактов
2. [Где?] Определение кол-ва слоев полупроводников и распределение проводников по слоям
3. [Когда?] В каком порядке проводить соединения
4. [Как?] Выполнение собственно трассировки

Рассмотрим этап 2 из [ГДЕ?] - определение количества слоев полупроводников и распределение проводников по слоям. Возможны два подхода:
1. Заполняем первый слой, пока это возможно. Затем заполняем второй и так далее. Недостаток: жадный алгоритм, решение может быть неоптимальным. Неравномерное распределение проводников по слоям.
2. Определяют факт пересечения проводников в одном слое, затем по этой информации определяют необходимое количество слоев и распределение проводников.

Определение факта пересечения:
1. В неортогональной метрике - по факту пересечения отрезков.
2. В ортогональной метрике - по факту пересечения прямоугольников.

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

Хроматическое число графа - минимальное количество цветов, в которое можно раскрасить граф так, что никакие две смежные вершины не будут окрашены в один цвет. В нашей задаче каждому цвету, в который раскрашен граф пересечений, соответствует отдельный слой полупроводников.