<HTML> <!-- Copyright 2007 Aaron Windsor Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> <Head> <Title>Boost Graph Library: Chrobak-Payne Straight Line Drawing</Title> <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" ALINK="#ff0000"> <IMG SRC="../../../boost.png" ALT="C++ Boost" width="277" height="86"> <BR Clear> <H1>Chrobak-Payne Straight Line Drawing</H1> <p> <pre> 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 ); </pre> <br> <p> A <i>straight line drawing</i> of a <a href="./planar_graphs.html#planar"> planar graph</a> is a <a href="./planar_graphs.html#plane_drawing">plane drawing</a> 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. <tt>chrobak_payne_straight_line_drawing</tt> uses an algorithm of Chrobak and Payne [<a href = "./bibliography.html#chrobakpayne95">71</a>] to form a straight line drawing of a planar graph by mapping all <i>n</i> vertices in a planar graph to integer coordinates in a <i>(2n - 4) x (n - 2)</i> grid. <center> <img src="./figs/straight_line_drawing.png"> </center> <p> The input graph passed to <tt>chrobak_payne_straight_line_drawing</tt> must be a <a href="make_maximal_planar.html">maximal planar graph</a> 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 <i>g</i>, you can create a copy <i>g'</i> of <i>g</i>, store a mapping <i>m</i> of vertices in <i>g'</i> to vertices in <i>g</i>, <a href="make_maximal_planar.html">triangulate</a> <i>g'</i>, and then send <i>g'</i> in as the input to <tt>chrobak_payne_straight_line_drawing</tt>. The drawing returned can then be applied to <i>g</i> using <i>m</i> to translate vertices from one graph to another, since <i>g</i> contains a subset of the edges in <i>g'</i>. <h3>Complexity</h3> If the vertex index map provides constant-time access to indices, this function takes time <i>O(n + m)</i> for a planar graph with <i>n</i> vertices and <i>m</i> edges. Note that in a simple planar graph with <i>f</i> faces, <i>m</i> edges, and <i>n</i> vertices, both <i>f</i> and <i>m</i> are <i>O(n)</i>. <H3>Where Defined</H3> <P> <a href="../../../boost/graph/chrobak_payne_drawing.hpp"> <TT>boost/graph/chrobak_payne_drawing.hpp</TT> </a> <h3>Parameters</h3> IN: <tt>Graph& g</tt> <blockquote> An undirected graph. The graph type must be a model of <a href="VertexListGraph.html">Vertex List Graph</a> </blockquote> IN <tt>PlanarEmbedding embedding</tt> <blockquote> A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map </a> that models the <a href="PlanarEmbedding.html">PlanarEmbedding</a> concept. </blockquote> IN <tt>ForwardIterator</tt> <blockquote> A ForwardIterator that has <tt>value_type</tt> equal to <tt>graph_traits<Graph>::vertex_descriptor</tt>. </blockquote> OUT: <tt>PositionMap</tt> <blockquote> A <a href="../../property_map/doc/LvaluePropertyMap.html">Writable LValue Property Map</a> that models the Position Map concept. The Position Map concept requires that the value mapped to be an object that has members <tt>x</tt> and <tt>y</tt>. For example, if <tt>p</tt> models PositionMap and <tt>v</tt> is a vertex in the graph, <tt>p[v].x</tt> and <tt>p[v].y</tt> are valid expressions. The type of <tt>x</tt> and <tt>y</tt> must be implicitly convertable to <tt>std::size_t</tt>. </blockquote> IN: <tt>VertexIndexMap vm</tt> <blockquote> A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map </a> that maps vertices from <tt>g</tt> to distinct integers in the range <tt>[0, num_vertices(g) )</tt><br> <b>Default</b>: <tt>get(vertex_index,g)</tt><br> </blockquote> <H3>Example</H3> <P> <a href="../example/straight_line_drawing.cpp"> <TT>examples/straight_line_drawing.cpp</TT> </a> <h3>See Also</h3> <p> <ul> <li> <a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a> <li> <a href="is_straight_line_drawing.html"><tt>is_straight_line_drawing</tt> </a> </ul> <br> <HR> Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com"> aaron.windsor@gmail.com</a>) </BODY> </HTML>