Configuration options for planarity testing and auxiliary outputs. More...

#include <Planarity_Test.H>

Collaboration diagram for Aleph::Planarity_Test_Options:

Public Attributes
bool	compute_embedding = false
	If true and the graph is found to be planar, computes a combinatorial embedding (rotation system and list of faces).

bool	embedding_prefer_lr_linear = true
	If true, the algorithm tries to construct the embedding using a linear-time Left-Right (LR) heuristic first.

bool	embedding_allow_bruteforce_fallback = true
	If the LR heuristic fails to find a valid embedding, allows falling back to an exact but potentially exponential-time search.

bool	embedding_validate_with_euler = true
	If true, validates the generated rotation system using Euler's formula ( \(V - E + F = 1 + C\)) to ensure it is a valid planar embedding.

bool	compute_nonplanar_certificate = false
	If true and the graph is found to be non-planar, attempts to extract a Kuratowski subdivision (K5 or K3,3) or a minimal non-planar subgraph as a witness.

size_t	embedding_max_combinations = 300000
	Maximum number of candidate rotations to evaluate during embedding search or repair.

size_t	certificate_max_edges = 180
	Maximum number of edges in the simplified graph allowed for full non-planarity witness extraction.

size_t	certificate_max_branch_nodes_search = 24
	Maximum size of the core subgraph allowed for exhaustive Kuratowski pattern searching.

size_t	certificate_max_reduction_passes = std::numeric_limits<size_t>::max()
	Maximum number of global passes in the edge-reduction loop for minimal obstruction extraction.

Detailed Description

Configuration options for planarity testing and auxiliary outputs.

Provides control over whether to compute advanced outputs (embedding, non-planarity witnesses) and sets search bounds for these potentially expensive operations.

Definition at line 148 of file Planarity_Test.H.

Member Data Documentation

◆ certificate_max_branch_nodes_search

size_t Aleph::Planarity_Test_Options::certificate_max_branch_nodes_search = 24

Maximum size of the core subgraph allowed for exhaustive Kuratowski pattern searching.

Definition at line 194 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate().

◆ certificate_max_edges

size_t Aleph::Planarity_Test_Options::certificate_max_edges = 180

Maximum number of edges in the simplified graph allowed for full non-planarity witness extraction.

Definition at line 189 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate().

◆ certificate_max_reduction_passes

size_t Aleph::Planarity_Test_Options::certificate_max_reduction_passes = std::numeric_limits<size_t>::max()

Maximum number of global passes in the edge-reduction loop for minimal obstruction extraction.

Definition at line 199 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate().

◆ compute_embedding

bool Aleph::Planarity_Test_Options::compute_embedding = false

If true and the graph is found to be planar, computes a combinatorial embedding (rotation system and list of faces).

Note: Computing the embedding can be significantly more expensive than just testing for planarity.

Definition at line 156 of file Planarity_Test.H.

Referenced by main(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::simple_edges_are_planar(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ compute_nonplanar_certificate

bool Aleph::Planarity_Test_Options::compute_nonplanar_certificate = false

If true and the graph is found to be non-planar, attempts to extract a Kuratowski subdivision (K5 or K3,3) or a minimal non-planar subgraph as a witness.

Definition at line 179 of file Planarity_Test.H.

Referenced by Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::run(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().