WikiEdge:ArXiv-2409.01889v1/terms
跳转到导航
跳转到搜索
- 弱化层次平面图（Weakly Leveled Planar Graph）：在这种图中，每个顶点表示为沿水平线（称为层级）的点，每条边要么是水平线段，要么是严格单调的曲线。
- 边跨度（Edge Span）：边跨度是指边所触及的层级数减一。
- 参数化复杂性（Parameterized Complexity）：研究问题在特定参数限制下的可解性，特别是当参数较小时问题是否可以在多项式时间内解决。
- 核化（Kernelization）：一种减少问题规模的技术，通过转换为一个等价的、规模更小的实例（核），使得核的规模与参数成函数关系。
- 树宽（Treewidth）：图的树宽是其树宽分解中的最大团的数量减一，树宽分解是一种将图分解为树结构的方法。
- 平面图（Planar Graph）：平面图是一种可以在平面上绘制而不使边相交的图。
- 外平面图（Outerplanar Graph）：外平面图是一种特殊类型的平面图，其中所有顶点都位于图的外部面。
- 2-外平面图（2-Outerplanar Graph）：2-外平面图是一种平面图，通过移除外部顶点可以得到一个外平面图。
- 层级平面图（Level Planar Graph）：层级平面图是一种特殊类型的平面图，其中顶点被分配到水平线上，并且边只连接相邻层级的顶点。
- 树深（Treedepth）：树深是图的树深分解中的最小深度，树深分解是一种树形结构，其中图的每个顶点都是树中的一个节点。