Planarity_Test.H File Reference

Planarity testing on Aleph graphs. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <sstream>
#include <string>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>
#include <tpl_dynMapTree.H>
#include <tpl_dynSetTree.H>
#include <tpl_graph.H>

Include dependency graph for Planarity_Test.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Planarity_Test_Options
	Configuration for planarity test optional outputs. More...
struct	Aleph::Planarity_Test_Result< GT >
	Result of planarity testing. More...
struct	Aleph::Planarity_Test_Result< GT >::Rotation_Entry
struct	Aleph::Planarity_Test_Result< GT >::Edge_Witness
struct	Aleph::Planarity_Test_Result< GT >::Path_Witness
struct	Aleph::Planar_Dual_Edge_Info< GT >
	Dual-edge payload linked to a primal simplified edge. More...
struct	Aleph::Planar_Dual_Metadata< GT >
	Metadata extracted from a planar embedding for face/dual analysis. More...
struct	Aleph::Planar_Dual_Metadata< GT >::Face_Dart
struct	Aleph::Planar_Dual_Metadata< GT >::Face_Boundary
struct	Aleph::Planar_Geometric_Drawing_Options
	Options for embedding-aware 2D drawing extraction. More...
struct	Aleph::Planar_Geometric_Drawing< GT >
	Embedding-aware geometric drawing result. More...
struct	Aleph::Planar_Geometric_Drawing< GT >::Node_Position
struct	Aleph::NonPlanar_Certificate_Export_Options
	Export options for non-planar certificate serializers. More...
struct	Aleph::NonPlanar_Certificate_Validation< GT >
	Structural validation report for non-planar certificates. More...
struct	Aleph::Dft_Certificate_Node_Label< GT >
	Default node labeler for certificate export. More...
struct	Aleph::planarity_detail::Edge_Key
struct	Aleph::planarity_detail::Simple_Edge
struct	Aleph::planarity_detail::Interval
struct	Aleph::planarity_detail::Conflict_Pair
struct	Aleph::planarity_detail::Dart_Key
struct	Aleph::planarity_detail::Compressed_Path
class	Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >
class	Aleph::Planarity_Test< GT, SA >
	Functor wrapper for planarity_test(). More...
class	Aleph::Is_Planar_Graph< GT, SA >
	Functor wrapper for is_planar_graph(). More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::planarity_detail

Typedefs
template<class GT >
using	Aleph::Default_Planar_Dual_Graph = List_Graph< Graph_Node< size_t >, Graph_Arc< Planar_Dual_Edge_Info< GT > > >

Enumerations
enum class	Aleph::Planarity_Certificate_Type { Aleph::Planarity_Certificate_Type::None , Aleph::Planarity_Certificate_Type::K5_Subdivision , Aleph::Planarity_Certificate_Type::K33_Subdivision , Aleph::Planarity_Certificate_Type::Minimal_NonPlanar_Obstruction }
	Non-planarity witness classification. More...

Functions
const char *	Aleph::to_string (const Planarity_Certificate_Type type) noexcept
	Return readable name for certificate type.
bool	Aleph::planarity_detail::interval_empty (const Interval &i) noexcept
bool	Aleph::planarity_detail::pair_empty (const Conflict_Pair &p) noexcept
std::string	Aleph::planarity_detail::json_escape_string (const std::string &s)
std::string	Aleph::planarity_detail::dot_escape_string (const std::string &s)
std::string	Aleph::planarity_detail::xml_escape_string (const std::string &s)
template<class PtrT >
std::string	Aleph::planarity_detail::pointer_to_string (const PtrT ptr)
template<class GT >
void	Aleph::planarity_detail::collect_certificate_nodes (const Planarity_Test_Result< GT > &result, Array< typename GT::Node * > &nodes, DynMapTree< typename GT::Node *, size_t > &node_to_id)
double	Aleph::planarity_detail::orient2d (const double ax, const double ay, const double bx, const double by, const double cx, const double cy) noexcept
bool	Aleph::planarity_detail::bounding_boxes_intersect (const double ax, const double ay, const double bx, const double by, const double cx, const double cy, const double dx, const double dy) noexcept
bool	Aleph::planarity_detail::segments_properly_intersect (const double ax, const double ay, const double bx, const double by, const double cx, const double cy, const double dx, const double dy) noexcept
template<class GT , class SA = Dft_Show_Arc<GT>>
Planarity_Test_Result< GT >	Aleph::planarity_test (const GT &g, SA sa=SA(), const Planarity_Test_Options &options=Planarity_Test_Options())
	Execute planarity test on an Aleph graph.
template<class GT >
Planarity_Test_Result< GT >	Aleph::planarity_test (const GT &g, const Planarity_Test_Options &options)
	Overload with default arc selector.
template<class GT , class SA = Dft_Show_Arc<GT>>
bool	Aleph::is_planar_graph (const GT &g, SA sa=SA(), const Planarity_Test_Options &options=Planarity_Test_Options())
	Convenience boolean API for planarity.
template<class GT >
bool	Aleph::is_planar_graph (const GT &g, const Planarity_Test_Options &options)
	Overload with default arc selector.
template<class GT >
Planar_Dual_Metadata< GT >	Aleph::planar_dual_metadata (const Planarity_Test_Result< GT > &result)
	Build face and dual-edge metadata from a planar embedding result.
template<class GT , class DGT = Default_Planar_Dual_Graph<GT>>
DGT	Aleph::build_planar_dual_graph (const Planar_Dual_Metadata< GT > &md)
	Build an Aleph dual graph from face/dual metadata.
template<class GT , class DGT = Default_Planar_Dual_Graph<GT>>
DGT	Aleph::build_planar_dual_graph (const Planarity_Test_Result< GT > &result)
	Build an Aleph dual graph directly from a planarity result.
template<class GT >
Planar_Geometric_Drawing< GT >	Aleph::planar_geometric_drawing (const Planarity_Test_Result< GT > &result, const Planar_Geometric_Drawing_Options &options=Planar_Geometric_Drawing_Options())
	Build embedding-aware 2D node coordinates from a planar result.
template<class GT , class Node_Label = Dft_Certificate_Node_Label<GT>>
std::string	Aleph::nonplanar_certificate_to_json (const Planarity_Test_Result< GT > &result, Node_Label node_label=Node_Label(), const NonPlanar_Certificate_Export_Options &options=NonPlanar_Certificate_Export_Options())
	Export non-planar certificate as JSON.
template<class GT , class Node_Label = Dft_Certificate_Node_Label<GT>>
std::string	Aleph::nonplanar_certificate_to_dot (const Planarity_Test_Result< GT > &result, Node_Label node_label=Node_Label(), const NonPlanar_Certificate_Export_Options &options=NonPlanar_Certificate_Export_Options())
	Export non-planar certificate as GraphViz DOT.
template<class GT >
NonPlanar_Certificate_Validation< GT >	Aleph::validate_nonplanar_certificate (const Planarity_Test_Result< GT > &result)
	Validate structural consistency of a non-planar certificate.
template<class GT >
bool	Aleph::nonplanar_certificate_is_valid (const Planarity_Test_Result< GT > &result)
	Convenience predicate over validate_nonplanar_certificate().
template<class GT , class Node_Label = Dft_Certificate_Node_Label<GT>>
std::string	Aleph::nonplanar_certificate_to_graphml (const Planarity_Test_Result< GT > &result, Node_Label node_label=Node_Label(), const NonPlanar_Certificate_Export_Options &options=NonPlanar_Certificate_Export_Options())
	Export non-planar certificate as GraphML.
template<class GT , class Node_Label = Dft_Certificate_Node_Label<GT>>
std::string	Aleph::nonplanar_certificate_to_gexf (const Planarity_Test_Result< GT > &result, Node_Label node_label=Node_Label(), const NonPlanar_Certificate_Export_Options &options=NonPlanar_Certificate_Export_Options())
	Export non-planar certificate as GEXF.

Variables
static constexpr size_t	Aleph::planarity_detail::Null_Edge = std::numeric_limits<size_t>::max()

Detailed Description

Planarity testing on Aleph graphs.

This header provides a dedicated API to test whether a graph is planar, with optional combinatorial embedding and optional non-planarity witness.

Problem solved

Decide if a graph can be drawn on the plane with no edge crossings.

Notes on input model

The test is performed on the underlying undirected simple graph:

• arc orientation is ignored for digraphs,
• self-loops are ignored,
• parallel arcs are collapsed.

This normalization preserves planarity.

Core algorithm

The core checker uses the Left-Right planarity test (de Fraysseix-Rosenstiehl / Brandes style), with:

• DFS orientation,
• lowpoint / lowpoint2 values,
• conflict-pair stack constraints.

Optional advanced outputs

• Combinatorial embedding (rotation system + face walk summary): LR construction first, then bounded deterministic LR-local repair (reversals/swaps, multi-start coordinate descent), with optional bounded exact fallback.
• Embedding-aware geometric drawing: 2D node coordinates with harmonic relaxation and optional crossing validation.
• Certificate export: machine-readable JSON, DOT, GraphML and GEXF serializers.
• Certificate structural validation: checks witness internal consistency before external-tool ingestion.
• Non-planarity witness:
  • Kuratowski subdivision classification (K5 or K3,3) on branch-core search,
  • otherwise a minimal non-planar obstruction (edge-minimal by deletion).

Complexity

• Normalization: O(E log E)
• LR planarity test on simplified graph: O(V + E)
• Optional embedding:
  • LR-first + bounded LR-local repair
  • optional bounded exponential exact fallback
• Optional certificate extraction: O(M * (V + E)) LR invocations in practice

Definition in file Planarity_Test.H.