A Four-Colorable Algorithm for Planar Graph Based on Path Homotopy Search
Banghuang Peng · 2025
In this paper, a four-color coloring algorithm for maximal planar graphs with finite boundary is proposed, which aims to explore the four-color coloring method for complex planar graphs. Firstly, the surrounding coloring graph model is introduced to realize the unified decomposition and local connectivity processing of the maximum planar graph; secondly, each adjacent boundary path is constructed based on the connectivity characteristics of the combined surrounding module, and each path is colored in coordination; thirdly, each adjacent path is colored by using the width search of path homotopy for internal endpoints, and local conflict coloring is checked; And finally, carrying out encircling coloring on the end points of the combined encircling module constructed by the end points under the potential well effect of adjacent path search so as to complete the coloring processing of the whole plane graph. At the same time, this paper analyzes the feasibility and complexity of the coloring algorithm, aiming to provide an efficient and feasible four-color coloring algorithm for planar graphs, and promote its wide application in graphic design, map drawing, circuit board layout and other fields.