lal::detail::Dmin::planar Namespace Reference

In planar arrangements. More...

Functions
template<bool make_arrangement>
std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t >	AEF (const graphs::free_tree &t) noexcept
	Minimum planar arrangement of a free tree. More...
template<bool make_arrangement>
std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t >	HS (const graphs::free_tree &t) noexcept
	Minimum planar arrangement of a free tree. More...

Detailed Description

In planar arrangements.

Function Documentation

AEF()

template<bool make_arrangement>

std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t > lal::detail::Dmin::planar::AEF ( const graphs::free_tree &  t )

noexcept

Minimum planar arrangement of a free tree.

This function first constructs the sorted adjacency matrix rooted at one of the tree's centroidal vertices. Then, it arranges the tree so that there are no edge crossings and the centroidal vertex is not covered. Such arrangement is done using an interval-based algorithm.

This function implements the algorithm in [7].

Template Parameters

make_arrangement

Construct a maximum arrangement.

Parameters

t	Input tree.

Returns

A pair of cost and minimum linear arrangement.

HS()

template<bool make_arrangement>

std::conditional_t< make_arrangement, std::pair< uint64_t, linear_arrangement >, uint64_t > lal::detail::Dmin::planar::HS ( const graphs::free_tree &  t )

noexcept

Minimum planar arrangement of a free tree.

This function first constructs the sorted adjacency matrix rooted at one of the tree's centroidal vertices. Then, it arranges the tree so that there are no edge crossings and the centroidal vertex is not covered. Such arrangement is done using an displacement-based algorithm.

This function implements the algorithm following the description in [7], i.e., this algorithm uses the approach first described by Hochberg and Stallmann in [24] using the correction in [7].

Template Parameters

make_arrangement

Construct a maximum arrangement.

Parameters

t	Input tree.

Returns

A pair of cost and minimum linear arrangement.