Chrobak-Payne Straight Line Drawing

Creates a straight line drawing of a maximal planar graph on an integer grid.

Complexity: O(n + m)
Defined in: <boost/graph/chrobak_payne_drawing.hpp>

Synopsis

template <typename Graph, typename PlanarEmbedding,
          typename ForwardIterator, typename PositionMap,
          typename VertexIndexMap>
void chrobak_payne_straight_line_drawing(
    const Graph& g,
    PlanarEmbedding perm,
    ForwardIterator ordering_begin,
    ForwardIterator ordering_end,
    PositionMap drawing,
    VertexIndexMap vm);

Direction Parameter Description

Direction	Parameter	Description
IN	`const Graph& g`	An undirected graph. The type `Graph` must be a model of VertexListGraph.
IN	`PlanarEmbedding perm`	A Readable Property Map that models the PlanarEmbedding concept.
IN	`ForwardIterator ordering_begin, ordering_end`	A ForwardIterator range with `value_type` equal to `graph_traits<Graph>::vertex_descriptor`, representing a canonical ordering of the vertices.
OUT	`PositionMap drawing`	A Writable LValue Property Map that models the Position Map concept. The value mapped to must be an object with members `x` and `y`. For example, if `p` models PositionMap and `v` is a vertex, `p[v].x` and `p[v].y` are valid expressions. The type of `x` and `y` must be implicitly convertible to `std::size_t`.
IN	`VertexIndexMap vm`	A Readable Property Map that maps vertices from `g` to distinct integers in the range `[0, num_vertices(g))`. Default: `get(vertex_index, g)`

const Graph& g

An undirected graph. The type Graph must be a model of VertexListGraph.

PlanarEmbedding perm

A Readable Property Map that models the PlanarEmbedding concept.

ForwardIterator ordering_begin, ordering_end

A ForwardIterator range with value_type equal to graph_traits<Graph>::vertex_descriptor, representing a canonical ordering of the vertices.

OUT

PositionMap drawing

A Writable LValue Property Map that models the Position Map concept. The value mapped to must be an object with members x and y. For example, if p models PositionMap and v is a vertex, p[v].x and p[v].y are valid expressions. The type of x and y must be implicitly convertible to std::size_t.

VertexIndexMap vm

A Readable Property Map that maps vertices from g to distinct integers in the range [0, num_vertices(g)).
Default: get(vertex_index, g)

Description

A straight line drawing of a planar graph is a plane drawing where each edge is drawn using a straight line segment. Since all edges are line segments, the drawing is completely determined by the placement of vertices in the plane. chrobak_payne_straight_line_drawing uses an algorithm of Chrobak and Payne [65] to form a straight line drawing of a planar graph by mapping all n vertices in a planar graph to integer coordinates in a (2n - 4) x (n - 2) grid.

The input graph passed to chrobak_payne_straight_line_drawing must be a maximal planar graph with at least 3 vertices. Self-loops and parallel edges are ignored by this function. Note that the restriction that the graph be maximal planar does not mean that this function can only draw maximal planar graphs (the graph pictured above is not maximal planar, for example). If you want to draw a graph g, you can create a copy g' of g, store a mapping m of vertices in g' to vertices in g, triangulate g', and then send g' in as the input to chrobak_payne_straight_line_drawing. The drawing returned can then be applied to g using m to translate vertices from one graph to another, since g contains a subset of the edges in g'.

Example

See example/straight_line_drawing.cpp.

Edit this Page