A backtracking implementation for the 1-Planarity problem. More...

#include <ogdf/k-planarity/1-planarity_backtracking/OnePlanarityBacktracking.h>

Inheritance diagram for ogdf::oneplan_backtracking::OnePlanarityBacktracking:

Classes
class	DFSThread
	A class representing one depth-first search in the backtracking tree. More...

Public Member Functions
	OnePlanarityBacktracking (const OnePlanarityBacktracking &)=delete

	OnePlanarityBacktracking (int maxThreads=1000, int maxKuratowskis=1000)
	Creates a new solver.

virtual	~OnePlanarityBacktracking ()

OnePlanarityBacktracking &	operator= (const OnePlanarityBacktracking &)=delete

int	processedNodes () const
	Returns the number of search tree nodes that were processed in the previous run.

Module::ReturnType	testICPlanarity (const Graph &G, OnePlanarization *out=nullptr)
	Tests whether `G` is IC-Planar.

Module::ReturnType	testNICPlanarity (const Graph &G, OnePlanarization *out=nullptr)
	Tests whether `G` is NIC-Planar.

Module::ReturnType	testOnePlanarity (const Graph &G, OnePlanarization *out=nullptr)
	Tests whether `G` is 1-planar.

Public Member Functions inherited from ogdf::Timeouter
	Timeouter ()
	timeout is turned of by default

	Timeouter (bool t)
	timeout is turned off (false) or on (true) (with 0 second)

	Timeouter (const Timeouter &t)

	Timeouter (double t)
	timeout is set to the given value (seconds)

	~Timeouter ()

bool	isTimeLimit () const
	returns whether any time limit is set or not

Timeouter &	operator= (const Timeouter &t)

double	timeLimit () const
	returns the current time limit for the call

void	timeLimit (bool t)
	shorthand to turn timelimit off or on (with 0 seconds)

void	timeLimit (double t)
	sets the time limit for the call (in seconds); <0 means no limit.

Protected Attributes
std::vector< std::unique_ptr< PartialSolutionFilter > >	m_filters

Protected Attributes inherited from ogdf::Timeouter
double	m_timeLimit
	Time limit for module calls (< 0 means no limit).

Private Types
enum class	NodeStatus { CNT , CUT , SOL }
	Classification of partial solutions in the search tree. More...

Private Member Functions
void	push (DFSThread t, EdgePairPartition epp)
	Creates a new DFS-thread for `epp` if there is space, otherwise pushes it to `t`.

Module::ReturnType	test (OneplanMode mode, const Graph &G, OnePlanarization *out=nullptr)
	Runs the backtracking on `G` and writes the solution to `out`.

NodeStatus	verifyNode (EdgePairPartition *epp)
	Determines whether a partial solution is a solution, non-realizable, or the search must continue.

Private Attributes
int	m_maxExtractedKuratowskis

int	m_maxThreads

int	m_processedNodes = 0

std::list< DFSThread >	m_threads

Detailed Description

A backtracking implementation for the 1-Planarity problem.

Implements the best configuration of the backtracking procedure for 1-Planarity evaluated in:

Remarks: Simon D. Fink, Miriam Münch, Matthias Pfretzschner and Ignaz Rutter. Heuristics for Exact 1-Planarity Testing. To appear in the Proc. of the 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025, LIPIcs, Volume 357, 2025.

This solver finds edge pairs to branch over by extracting multiple Kuratowski-Subdivisions of the graph and uses filters to reject non-realizable partial solutions early to shrink the search space. Moreover, it explores the search space using multiple depth-first searches running alternatingly to increase the likelihood of finding solutions with few crossings early.

Definition at line 64 of file OnePlanarityBacktracking.h.

Member Enumeration Documentation

◆ NodeStatus

enum class ogdf::oneplan_backtracking::OnePlanarityBacktracking::NodeStatus

strongprivate

Classification of partial solutions in the search tree.

Enumerator
CNT	Unknown whether partial solution is realizable or not.
CUT	Partial solution is not realizable and can be rejected.
SOL	Partial solution is a solution.

Definition at line 110 of file OnePlanarityBacktracking.h.

Constructor & Destructor Documentation

◆ OnePlanarityBacktracking() [1/2]

ogdf::oneplan_backtracking::OnePlanarityBacktracking::OnePlanarityBacktracking	(	int	maxThreads = `1000`,
		int	maxKuratowskis = `1000`
	)

explicit

Creates a new solver.

Parameters

maxThreads	The maximum number of DFS-threads that are executed alternatingly. A higher number may help find solutions with few crossings faster, but comes at a cost of increased memory consumption.
maxKuratowskis	The maximum number of Kuratowski-Subdivisions that are taken into consideration when branching. A higher number may shrink the search space, but increases the time spent at each node in the search tree.

◆ ~OnePlanarityBacktracking()

virtual ogdf::oneplan_backtracking::OnePlanarityBacktracking::~OnePlanarityBacktracking ( )

virtual

◆ OnePlanarityBacktracking() [2/2]

ogdf::oneplan_backtracking::OnePlanarityBacktracking::OnePlanarityBacktracking ( const OnePlanarityBacktracking & )

delete

Member Function Documentation

◆ operator=()

OnePlanarityBacktracking & ogdf::oneplan_backtracking::OnePlanarityBacktracking::operator= ( const OnePlanarityBacktracking & )

delete

◆ processedNodes()

int ogdf::oneplan_backtracking::OnePlanarityBacktracking::processedNodes ( ) const

inline

Returns the number of search tree nodes that were processed in the previous run.

Definition at line 193 of file OnePlanarityBacktracking.h.

◆ push()

void ogdf::oneplan_backtracking::OnePlanarityBacktracking::push	(	DFSThread *	t,
		EdgePairPartition *	epp
	)

private

Creates a new DFS-thread for epp if there is space, otherwise pushes it to t.

◆ test()

Module::ReturnType ogdf::oneplan_backtracking::OnePlanarityBacktracking::test	(	OneplanMode	mode,
		const Graph &	G,
		OnePlanarization *	out = `nullptr`
	)

private

Runs the backtracking on G and writes the solution to out.

◆ testICPlanarity()

Module::ReturnType ogdf::oneplan_backtracking::OnePlanarityBacktracking::testICPlanarity	(	const Graph &	G,
		OnePlanarization *	out = `nullptr`
	)

inline

Tests whether G is IC-Planar.

A graph is IC-Planar if it admits a drawing with at most one crossing per edge and no two crossed edges may share an endpoint.

Parameters

G	is the input graph.
out	is assigned a solution, if one is found.

Returns: Module::ReturnType::TimeoutInfeasible if a timeLimit() was specified and exceeded. Otherwise returns Module::ReturnType::Feasible if G is IC-planar and Module::ReturnType::NoFeasibleSolution if it is not.

Remarks: In contrast to 1-Planarity and NIC-Planarity, a graph is not necessarily IC-planar if and only if its biconnected components are.

Definition at line 171 of file OnePlanarityBacktracking.h.

◆ testNICPlanarity()

Module::ReturnType ogdf::oneplan_backtracking::OnePlanarityBacktracking::testNICPlanarity	(	const Graph &	G,
		OnePlanarization *	out = `nullptr`
	)

inline

Tests whether G is NIC-Planar.

A graph is NIC-Planar if it admits a drawing with at most one crossing per edge and two pairs of crossed edges may have at most one common endpoint.

Parameters

G	is the input graph.
out	is assigned a solution, if one is found.

Returns: Module::ReturnType::TimeoutInfeasible if a timeLimit() was specified and exceeded. Otherwise returns Module::ReturnType::Feasible if G is NIC-planar and Module::ReturnType::NoFeasibleSolution if it is not.

Remarks: For better performance, first decompose the graph into its biconnected components.

Definition at line 188 of file OnePlanarityBacktracking.h.

◆ testOnePlanarity()

Module::ReturnType ogdf::oneplan_backtracking::OnePlanarityBacktracking::testOnePlanarity	(	const Graph &	G,
		OnePlanarization *	out = `nullptr`
	)

inline

Tests whether G is 1-planar.

A graph is 1-planar if it admits a drawing with at most one crossing per edge.

Parameters

G	is the input graph.
out	is assigned a solution, if one is found.

Returns: Module::ReturnType::TimeoutInfeasible if a timeLimit() was specified and exceeded. Otherwise returns Module::ReturnType::Feasible if G is 1-planar and Module::ReturnType::NoFeasibleSolution if it is not.

Remarks: For better performance, first decompose the graph into its biconnected components.

Definition at line 152 of file OnePlanarityBacktracking.h.

◆ verifyNode()

NodeStatus ogdf::oneplan_backtracking::OnePlanarityBacktracking::verifyNode ( EdgePairPartition * epp )

private

Determines whether a partial solution is a solution, non-realizable, or the search must continue.

Member Data Documentation

◆ m_filters

std::vector<std::unique_ptr<PartialSolutionFilter> > ogdf::oneplan_backtracking::OnePlanarityBacktracking::m_filters

protected

Definition at line 196 of file OnePlanarityBacktracking.h.

◆ m_maxExtractedKuratowskis

int ogdf::oneplan_backtracking::OnePlanarityBacktracking::m_maxExtractedKuratowskis

private

Definition at line 119 of file OnePlanarityBacktracking.h.

◆ m_maxThreads

int ogdf::oneplan_backtracking::OnePlanarityBacktracking::m_maxThreads

private

Definition at line 118 of file OnePlanarityBacktracking.h.

◆ m_processedNodes

int ogdf::oneplan_backtracking::OnePlanarityBacktracking::m_processedNodes = 0

private

Definition at line 120 of file OnePlanarityBacktracking.h.

◆ m_threads

std::list<DFSThread> ogdf::oneplan_backtracking::OnePlanarityBacktracking::m_threads

private

Definition at line 116 of file OnePlanarityBacktracking.h.

The documentation for this class was generated from the following file:

include/ogdf/k-planarity/1-planarity_backtracking/OnePlanarityBacktracking.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Protected Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ NodeStatus

Constructor & Destructor Documentation

◆ OnePlanarityBacktracking() [1/2]

◆ ~OnePlanarityBacktracking()

◆ OnePlanarityBacktracking() [2/2]

Member Function Documentation

◆ operator=()

◆ processedNodes()

◆ push()

◆ test()

◆ testICPlanarity()

◆ testNICPlanarity()

◆ testOnePlanarity()

◆ verifyNode()

Member Data Documentation

◆ m_filters

◆ m_maxExtractedKuratowskis

◆ m_maxThreads

◆ m_processedNodes

◆ m_threads

Open
Graph Drawing
Framework