On coloring earth/moon maps and its application to the testing of printed circuit boards

• Main Author: Ghimire, Sabina C.
• Format: text
• Language: English
• Published: Animo Repository 1997
• Subjects: Mappings (Mathematics); Graph theory; Printed circuits; Algorithms; Map-coloring problem; Mathematics
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/1870
• Institution: De La Salle University

This thesis presents two main topics on map-coloring. The first involves coloring Earth/Moon maps. With the assumption that the moon is colonized, the maps on the Earth and on the Moon are colored so that, every country on the Earth and its colony on the Moon receive the same color and that adjacent countries on the Earth and on the Moon receive different colors. This concept of coloring Earth/Moon maps is examined and explicitly discussed. The thickness t of a graph G defined as the minimum number of planar subgraphs of G whose union is G is used as a relevant tool for a more indepth discussion. The application of Earth/Moon coloring on testing printed circuit boards for erroneous electrical connections called short circuits is presented as the second topic of concern. The formulation of an efficient algorithm to detect such errors on printed circuit boards is explicated. In this study, the primary theorems are presented with proofs. Figures and graphs are provided for a vivid illustration of the theorems, problems and application. This paper explains in detail the two topics on the article Coloring Ordinary Maps, Maps of the Empires and Maps of the Moon by Joan Hutchinson.