Yog.Property.Planarity (YogEx v0.98.0)

Planarity testing and planar embedding for undirected graphs.

This module provides exact planarity checks using the Left-Right (LR) Planarity Test (de Fraysseix–Rosenstiehl), combinatorial embedding extraction, and Kuratowski witness identification.

Functions

Problem	Function	Complexity
Planar check	`planar?/1`	O(V^2)
Planar embedding	`planar_embedding/1`	O(V^3)
Kuratowski witness	`kuratowski_witness/1`	O(V^3)

Examples

iex> k5 = Yog.Generator.Classic.complete(5)
iex> Yog.Property.Planarity.planar?(k5)
false

iex> k33 = Yog.Generator.Classic.complete_bipartite(3, 3)
iex> Yog.Property.Planarity.planar?(k33)
false

Summary

Functions

kuratowski_witness(graph)

Identifies a Kuratowski witness (a subdivision of K5 or K3,3) that proves the graph is non-planar.

planar?(graph)

Returns true if the graph is planar (exactly).

planar_embedding(graph)

Returns a combinatorial embedding if the graph is planar.

Functions

kuratowski_witness(graph)

@spec kuratowski_witness(Yog.graph()) :: {:ok, map()} | :planar

Identifies a Kuratowski witness (a subdivision of K5 or K3,3) that proves the graph is non-planar.

planar?(graph)

@spec planar?(Yog.graph()) :: boolean()

Returns true if the graph is planar (exactly).

Uses the Left-Right (LR) Planarity Test (de Fraysseix–Rosenstiehl algorithm). It decomposes the graph into a DFS tree and back-edges, then determines if back-edges can be partitioned into "Left" and "Right" sides without crossing.

planar_embedding(graph)

@spec planar_embedding(Yog.graph()) :: {:ok, map()} | {:nonplanar, map()} | :nonplanar

Returns a combinatorial embedding if the graph is planar.