Three Color Algorithm for Two-Layer Printed Circuit Boards Layout with Minimum Via (최소 경유 2층 인쇄회로기판 배선도의 3-색 알고리즘)

Sang-Un, Lee (이상운)

Three Color Algorithm for Two-Layer Printed Circuit Boards Layout with Minimum Via

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2016, 21(3), pp.1-8
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science

Sang-Un, Lee ¹

¹강릉원주대학교

Accredited

ABSTRACT

The printed circuit board (PCB) can be used only 2 layers of front and back. Therefore, the wiring line segments are located in 2 layers without crossing each other. In this case, the line segment can be appear in both layers and this line segment is to resolve the crossing problem go through the via. The via minimization problem (VMP) has minimum number of via in layout design problem. The VMP is classified by NP-complete because of the polynomial time algorithm to solve the optimal solution has been unknown yet. This paper suggests polynomial time algorithm that can be solve the optimal solution of VMP. This algorithm transforms -line segments into vertices, and  -crossing into edges of a graph. Then this graph is partitioned into 3-coloring sets of each vertex in each set independent each other. For 3-coloring sets       , the  is assigned to front  ,  is back  , and  is   and connected with via. For the various experimental data, though this algorithm can be require   polynomial time, we obtain the optimal solution for all of data.

KEYWORDS

Via, Crossing, Coloring, Independent set, Two layer

Citation status

* References for papers published after 2023 are currently being built.

[journal] K.-S. The / 1991 / A layout modification approach to via minimization / IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems / Institute of Electrical and Electronics Engineers (IEEE) 10(4) : 536~541

[report] L. Franuke / 2011 / Via Minimization in VLSI Chip Design - Application of a Planar Max-Cut Algorithm / Cologne University : 1~15

[journal] M. R. Garey / 1983 / Crossing Number is NP-complete / SIAM Journal of Algorithmic Discrete Methods 4(3) : 312~316

[journal] N.J. Naclerio / 1989 / The via minimization problem is NP-complete / IEEE Transactions on Computers / Institute of Electrical and Electronics Engineers (IEEE) 38(11) : 1604~1608

[confproc] R. Hojati / 1990 / Layout Optimization by Pattern Modification / Proceedings of the 27th ACM/IEEE Design Automation Conference : 632~637

[confproc] S. C. Fang / 1991 / Constrained Via Minimization with Practical Considerations for Multi-Layer VLSI/PCB Routing Problems / Proceedings of the 28th ACM/IEEE Design Automation Conference : 60~65

[journal] Ruen-Wu Chen / 1983 / A graph-theoretic via minimization algorithm for two-layer printed circuit boards / IEEE Transactions on Circuits and Systems / Institute of Electrical and Electronics Engineers (IEEE) 30(5) : 284~299

[journal] Chi-Ping Hsu / 1983 / Minimum-Via Topological Routing / IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems / Institute of Electrical and Electronics Engineers (IEEE) 2(4) : 235~246

[journal] Y. S. Kuo / 1989 / Fast Algorithm for Optimal Layer Assignment / Integration, the VLSI Journal 7(3) : 231~245

[journal] Chin-Chih Chang / 1999 / An efficient approach to multilayer layer assignment with an application to via minimization / IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems / Institute of Electrical and Electronics Engineers (IEEE) 18(5) : 608~620

[journal] M. Marek-Sadowska / 1984 / An Unconstrained Topological Via Minimization Problem for Two-Layer Routing / IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems / Institute of Electrical and Electronics Engineers (IEEE) 3(3) : 184~190

[confproc] N. J. Naclerio / 1987 / Via Minimization for Gridless Layouts / Proceedings of the 24th ACM/IEEE Design Automation Conference : 159~165

[journal] S. Thakur / 1995 / An Optimal Layer Assignment Algorithm for Minimizing Crosstalk for Three Layer VHV Channel Routing / IEEE International Symposium on Circuits and Systems 1 : 207~210

[journal] M.J. Ciesielski / 1989 / Layer assignment for VLSI interconnect delay minimization / IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems / Institute of Electrical and Electronics Engineers (IEEE) 8(6) : 702~707

[confproc] K. Takahashi / 1998 / A Heuristic Algorithm to Solve Constrained Via Minimization for Three-Layer Routing Problems / Proceedings of the 1998 IEEE International Symposium on Circuits and Systems 6 : 254~257

[confproc] R. Noteboom / 1994 / A New Graph Coloring Algorithm for Constrained Via Minimization / Proceedings of the 37th Midwest Symposium on Circuits and Systems 1 : 363~366

[confproc] M. Tang / 1999 / A Genetic Algorithm for Constrained Via Minimization / Proceedings of the 6th International Conference on Neural Information Processing 2 : 435~440

[journal] P. Fouilhoux / 2004 / An Exact Model for Multi-Layer Constrained Via Minimization / IEEE Transactions on CAD of ICS xx(y)

[journal] R. B. Lin / 2007 / Conjugate Conflict Continuation Graphs for Multi-Layer Constrained Via Minimization / Information Sciences 177(12) : 2436~2447

[journal] P. Fouilhoux / 2012 / Solving VLSI Design and DNA Sequencing Problems Using Bipartization of Graphs / Computational Optimization and Applications 51(2) : 749~781

[book] N. A. Sherwani / 1999 / Via Minimization and Over-the-Cell Routing / Kluwer Academic Publishers Norwell

[confproc] X. Mu~n oz / 2001 / One Sided Crossing Minimization is NP-hard for Sparse Graphs / Graph Drawing GD’01, LNCS 2265 : 115~123

[journal] M. Newton / 2002 / Two New Heuristics for Two-Sides Bipartite Graph Drawing / Lecture Notes in Computer Science / Springer Berlin/Heidelberg 2528 : 465~485

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65