Grid-based Self-Aligned Quadruple Patterning aware two dimensional routing pattern

A routing grid for Self-Aligned Quadruple Patterning (SAQP) helps to find a valid routing of SAQP, but it is not easy to find it. The routing of SAQP on the grid consists of three types of routing. Among them, third type has turn prohibition constraint on the grid. Typical routing algorithms often fail to find a valid routing for third type. In this paper, SAQP compliant two dimensional routings are found on the grid by finding an optimal valid tertiary routing effectively. Experiments show that SAQP compliant routings are found efficiently.