图书推荐《平面图理论和算法》

周朝阳，生于1990年，拥有丰富的技术背景，现任成都沫茉商贸有限公司研发总监。公司将聚焦智能交通与智慧物流领域的技术突破，重点深耕车辆调度系统、三维装箱智能算法研发及路径规划三大方向，致力于以技术创新解决行业痛点，推动业务数字化、智能化转型

本书系统性地构建了从图论基础到平面图专项应用的完整知识体系，逻辑清晰，层层递进，兼具理论深度与算法实践价值。全书内容可概括为以下四个核心部分：

一、 图论与算法基础铺垫

本书首先奠定了必要的理论基础。在绪论中，回溯了图论自欧拉解决哥尼斯堡七桥问题以来的发展历程，并阐述了算法的核心特征（有穷性、确切性等）、思想（递归、分治等）及复杂度分析方法。同时，通过“货运计划智能助手”的案例，直观展现了平面图在现实世界中的巨大应用潜力。

第二章则系统地梳理了图论的核心知识，包括图的基本定义与分类（无向/有向、有权/无权、完全图、二分图等）、顶点的度与握手定理、图的基本操作、路径与连通性、匹配问题、欧拉图与哈密顿图的判定条件。此外，详细介绍了图的邻接矩阵和邻接表存储结构，深度优先搜索（DFS）与广度优先搜索（BFS）遍历算法，以及树与生成树的相关概念和性质，为后续学习提供了坚实的理论工具。

二、 平面图核心理论与判定方法

第三章是全书的理论核心，深入探讨了平面图的定义、性质与判定准则。它明确了可平面图与平面图的区别，引入了面、面次数等关键概念，并推导出平面图理论的基石——欧拉公式及其重要推论（如边数上限、最小度限制等），从而从理论上证明了K₅和K₃,₃是非平面图。

本章还介绍了极大平面图、外平面图等特殊平面图，以及对偶图、桥等概念。在判定方面，核心是库拉托夫斯基定理，它指出一个图是平面图当且仅当它不包含K₅或K₃,₃的细分。为了高效处理平面性判定中的顺序和结构问题，本章还讲解了PQ树、SPQR树和BC树等高级数据结构。

三、 平面性测试、嵌入与绘制关键技术

从理论转向实现，第四、五章聚焦于如何用算法判断和绘制平面图。

第四章详细讲解了平面性测试与嵌入算法。这包括基于回路分解的经典算法（如Auslander-Parter算法、线性时间的Hopcroft-Tarjan算法）和基于顶点插入的方法（如st-numbering与基于PQ树的算法）。重点拆解了Chiba-Nishizeki平面嵌入算法的两阶段线性时间流程，展示了如何将一个被判定为可平面的图实际计算出一个交叉免费的嵌入。

第五章则专注于平面图的可视化绘制。它介绍了各种绘制属性和风格（如直线图、凸图、正交图），并详细说明了用于高效存储和操作平面嵌入的DCEL（双连通边列表）数据结构。本章重点详解了两种在网格上绘制平面直线图的高效方法：移位法和realizer法。两者均能在线性时间内完成绘制，但realizer法在空间利用率上更具优势，体现了算法设计与优化的精妙。

四、 平面图专项定理与问题算法应用

最后，本书第六至第十章将平面图的强大能力应用于一系列经典应用上。

第六章介绍了平面图分离定理（如Lipton-Tarjan分离器、Miller环路分离器），这些定理是设计高效分治算法的基础。

第七章探讨了哈密顿回路问题，阐述了Tutte关于4连通平面图必存在哈密顿回路的定理，并介绍了相应的求解算法。

第八章讲解了顶点着色，利用平面图最小度不超过5的性质，详细描述了从六色到五色的着色算法。

第九章阐述了边着色问题，基于维津定理，给出了为平面图边着色的有效算法。

第十章处理了网络流问题，展示了如何利用平面图的特性及其对偶图，将最大流最小割定理应用于平面网络，从而更高效地求解单源单汇及多源多汇最大流问题。

全书特色与价值

本书构建了一个覆盖理论、算法与应用的完整知识体系。其内容组织严谨，从基础到前沿，从理论证明到算法伪代码与图形示例，讲解深入浅出。尤为突出的是，它对核心算法的时间复杂度进行了深度优化，多数达到了线性时间，极具工程实践价值。无论是对于从事算法研究、运筹优化、计算机图形学的科研人员，还是相关领域的工程技术人员，本书都是一部不可或缺的参考著作