Preserving Planarity in Graph Reductions

17 concepts13 papers

In computational complexity and algorithm design, reductions are the primary tool for translating one problem into another. To prove that a problem is hard, we map a known hard problem to it; to design an algorithm, we map our problem to one we already know how to solve.

Standard reductions treat graphs as abstract sets of vertices and edges. If two logical variables or paths need to interact, a standard reduction simply draws an edge between them. However, when working with planar graphs—graphs that can be drawn on a two-dimensional plane without any edges crossing—this abstract approach breaks down. Drawing arbitrary edges introduces crossings, destroying the planarity of the target graph and rendering planar-specific algorithms inapplicable.

To preserve planarity during a reduction, researchers must ensure that the target instance mimics the logic of the source instance entirely within a two-dimensional topological embedding. This requires specialized structural transformations and gadgets that resolve or bypass edge crossings without altering the underlying logic or solution counts of the problem.

The Planarity Dilemma and the Reduction Gap

Why can we not simply use standard graph transformations? Consider the classic problem of converting edge-based constraints to node-based constraints, or reducing general graph problems to restricted variants.

As Marx et al. and Chuzhoy et al. observe in the context of disjoint path problems, standard mathematical reductions often destroy the underlying topological properties of a graph. For instance, transforming an edge-disjoint path constraint into a vertex-disjoint constraint typically requires splitting edges or introducing auxiliary vertices that force crossings. This creates a "reduction gap," where algorithmic breakthroughs for one variant cannot be transferred to another because the reduction itself breaks the planarity that the algorithm relies on.

Simulating Crossings via Planar Crossover Gadgets

The most direct way to preserve planarity when mapping non-planar structures to a plane is to find a way to let two paths or signals "cross" each other conceptually without their edges physically intersecting. This is achieved using a planar crossover box.

   Signal A In          Signal B In
       \               /
        \             /
     +-------------------+
     |   Planar Logic    |  <-- Crossover Gadget
     |   Subgraph        |      (No internal crossings)
     +-------------------+
        /             \
       /               \
  Signal B Out        Signal A Out

As Hunt III et al. demonstrate, a crossover box is a localized, strictly planar subgraph that replaces an intersection. It is engineered so that information flowing from top-to-bottom and left-to-right passes through the gadget without interference, preserving the exact properties—such as the number of valid solutions—of the original non-planar formula.

This concept extends naturally to algebraic and constraint satisfaction frameworks. For example, Cai et al. and the authors utilize specialized algebraic matchgates to simulate edge crossings planarly. By matching the matrix signatures of the gadget to the logical requirements of a crossing, they prove that holographic algorithms can perfectly capture problems that are hard on general graphs but tractable on planar ones. Similarly, Jansen et al. employ degree-four vertex gadgets to resolve crossings in flow networks while maintaining a low treewidth, allowing them to establish parameterized complexity bounds.

Local Structural Replacements

Sometimes the challenge is not a crossing path, but a standard graph operation that inherently alters vertex degrees or connectivity in a non-planar way.

A classic example occurs when reducing a vertex-capacitated flow network to an edge-capacitated one. The textbook method splits each vertex $v$ into two nodes, $v_{in}$ and $v_{out}$, connected by a directed edge. If $v$ has edges connected to it from all directions on a plane, splitting it into two distinct nodes forces those edges to cross each other to reach their respective sides.

To circumvent this, Kaplan et al. replaced each high-degree vertex not with a pair of nodes, but with a cycle of edges.

Standard Splitting (Breaks Planarity):
     \  |  /                 \  |  /
      \ | /                   \ | /
     ---v---   ======>   v_in ------> v_out
      / | \                   / | \
     /  |  \                 /  |  \  (Edges must cross)

Planarity-Preserving Cycle Replacement:
         |                      |
       /   \                  /   \
     -v     v-   ======>     o-----o
      |     |                |     |  (Embedded cleanly
     -v     v-               o-----o   within the face)
       \   /                  \   /
         |                      |

Because a cycle can be embedded cleanly within the face of a planar graph, it preserves the geometric embedding while successfully delegating the vertex capacity to the cycle's edges, keeping specialized planar max-flow algorithms applicable.

Other structural replacements operate on similar principles:

  • Indicator Constructions: Dross et al. use planarity-preserving indicator gadgets to reduce graph homomorphism problems without introducing crossings.
  • Gadget-Based Triangulation: de Berg et al. transform complex geometric intersection graphs into planar representations by replacing high-degree intersection points with tree-like structures, enabling the use of planar separator theorems.

Why It Works: Bridging Constraints and Embeddings

The ultimate goal of these reductions is to unlock the powerful algorithmic toolkits available exclusively within the planar domain—such as the Four Color Theorem, planar separator theorems, or efficient parallel routines.

For instance, Hocquard et al. study exact square coloring, where vertices at distance exactly 2 must receive different colors. By transforming these distance-based constraints into standard adjacency problems via a planarity-preserving mapping, they can apply established planar coloring theorems directly to the modified graph.

In parallel complexity, Sankowski demonstrated that developing planarity-preserving reductions is the key to designing NC algorithms for weighted planar perfect matchings. By transforming problems into a form solvable by existing parallel algorithms without blowing up the graph's structural complexity, algorithmic power can be transferred across different problem types.

Even when simplifying a problem within the planar domain—such as reducing general perfect matchings to cubic planar matchings—Giannakos et al. showed that embedding the graph, constructing its dual, and strategically assigning degree-2 vertices to faces allows for degree regularization without introducing a single crossing.

Finally, this perspective helps minimize crossings when they are truly unavoidable. Chuzhoy et al. developed an augmented planarization strategy that identifies a specific set of edges to remove so that the remaining base graph mimics the structure of an optimal drawing. By ensuring the base graph preserves this near-optimal planar structure, they avoid the quadratic blow-up in edge crossings that typically occurs when re-inserting edges into a poorly chosen planar base.

Key Foundational Work

The Complexity of Planar Counting Problems (1998) — contributed 3 concept elements to this direction.
Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases (2000) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_planarity_preserving_reduction_f8c472bd,
  title = {planarity-preserving reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/planarity-preserving-reduction/rdr_f8c472bd9edd4dd7909bcaced395177e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_planarity_preserving_reduction_f8c472bd_v1,
  title = {planarity-preserving reduction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/planarity-preserving-reduction/rdr_f8c472bd9edd4dd7909bcaced395177e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake