Planar graphs with separation are dp-minimal

2022/05/20 by Javier de la Nuez González, González, Javier de la Nuez
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Cellular Automata and Applications

paper · pdf · doi:10.48550/arxiv.2205.10204

Abstract

We prove that given a planar embedding of a graph in the sphere the expansion of the graph structure by predicates encoding separation of vertices by simple cycles of the graph is dp-minimal.

Related

• A Simple Proof of the Existence of a Planar Separator
• Non-separating Planar Graphs
• Partitioning a Planar Graph into two Triangle-Forests
• Graphs avoiding immersion of K_3,3
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable