1<HTML> 2<!-- Copyright 2007 Aaron Windsor 3 4 Distributed under the Boost Software License, Version 1.0. 5 (See accompanying file LICENSE_1_0.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt) 7 8 --> 9<Head> 10<Title>Boost Graph Library: Chrobak-Payne Straight Line Drawing</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18<H1>Chrobak-Payne Straight Line Drawing</H1> 19 20<p> 21<pre> 22template<typename Graph, 23 typename PlanarEmbedding, 24 typename ForwardIterator, 25 typename PositionMap, 26 typename VertexIndexMap> 27void chrobak_payne_straight_line_drawing(const Graph& g, 28 PlanarEmbedding perm, 29 ForwardIterator ordering_begin, 30 ForwardIterator ordering_end, 31 PositionMap drawing, 32 VertexIndexMap vm 33 ); 34</pre> 35 36<br> 37<p> 38A <i>straight line drawing</i> of a <a href="./planar_graphs.html#planar"> 39planar graph</a> is a <a href="./planar_graphs.html#plane_drawing">plane 40drawing</a> where each edge is drawn using a straight line segment. Since all 41edges are line segments, the drawing is completely determined by the placement 42of vertices in the plane. <tt>chrobak_payne_straight_line_drawing</tt> uses an 43algorithm of Chrobak and Payne 44[<a href = "./bibliography.html#chrobakpayne95">71</a>] 45to form a straight 46line drawing of a planar graph by mapping all <i>n</i> vertices in a planar 47graph to integer coordinates in a <i>(2n - 4) x (n - 2)</i> grid. 48 49<center> 50<img src="./figs/straight_line_drawing.png"> 51</center> 52 53<p> 54The input graph passed to <tt>chrobak_payne_straight_line_drawing</tt> must 55be a <a href="make_maximal_planar.html">maximal planar graph</a> with at least 563 vertices. Self-loops and parallel edges are ignored by this function. Note 57that the restriction that the graph be maximal planar does not 58mean that this function can only draw maximal planar graphs (the graph pictured 59above is not maximal planar, for example). If you want to 60draw a graph <i>g</i>, you can create a copy <i>g'</i> of <i>g</i>, store a 61mapping <i>m</i> of vertices in <i>g'</i> to vertices in <i>g</i>, 62<a href="make_maximal_planar.html">triangulate</a> <i>g'</i>, and then send 63<i>g'</i> in as the input to <tt>chrobak_payne_straight_line_drawing</tt>. The 64drawing returned can then be applied to <i>g</i> using <i>m</i> to translate 65vertices from one graph to another, since <i>g</i> contains a subset of the 66edges in <i>g'</i>. 67 68 69 70<h3>Complexity</h3> 71 72If the vertex index map provides constant-time access to indices, this 73function takes time <i>O(n + m)</i> for a planar graph with <i>n</i> vertices 74and <i>m</i> edges. Note that 75in a simple planar graph with <i>f</i> faces, <i>m</i> edges, and <i>n</i> 76vertices, both <i>f</i> and <i>m</i> are <i>O(n)</i>. 77 78<H3>Where Defined</H3> 79 80<P> 81<a href="../../../boost/graph/chrobak_payne_drawing.hpp"> 82<TT>boost/graph/chrobak_payne_drawing.hpp</TT> 83</a> 84 85 86<h3>Parameters</h3> 87 88IN: <tt>Graph& g</tt> 89 90<blockquote> 91An undirected graph. The graph type must be a model of <a 92href="VertexListGraph.html">Vertex List Graph</a> 93</blockquote> 94 95IN <tt>PlanarEmbedding embedding</tt> 96 97<blockquote> 98A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map 99</a> that models the <a href="PlanarEmbedding.html">PlanarEmbedding</a> 100concept. 101</blockquote> 102 103IN <tt>ForwardIterator</tt> 104 105<blockquote> 106A ForwardIterator that has <tt>value_type</tt> equal to 107<tt>graph_traits<Graph>::vertex_descriptor</tt>. 108</blockquote> 109 110OUT: <tt>PositionMap</tt> 111 112<blockquote> 113A <a href="../../property_map/doc/LvaluePropertyMap.html">Writable LValue Property 114Map</a> that models the Position Map concept. The Position Map concept requires 115that the value mapped to be an object that has members <tt>x</tt> and 116<tt>y</tt>. For example, if <tt>p</tt> models PositionMap and <tt>v</tt> 117is a vertex in the graph, <tt>p[v].x</tt> and <tt>p[v].y</tt> are valid 118expressions. The type of <tt>x</tt> and <tt>y</tt> must be implicitly 119convertable to <tt>std::size_t</tt>. 120</blockquote> 121 122IN: <tt>VertexIndexMap vm</tt> 123 124<blockquote> 125A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map 126</a> that maps vertices from <tt>g</tt> to distinct integers in the range 127<tt>[0, num_vertices(g) )</tt><br> 128<b>Default</b>: <tt>get(vertex_index,g)</tt><br> 129</blockquote> 130 131 132 133<H3>Example</H3> 134 135<P> 136<a href="../example/straight_line_drawing.cpp"> 137<TT>examples/straight_line_drawing.cpp</TT> 138</a> 139 140<h3>See Also</h3> 141 142<p> 143<ul> 144<li> <a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a> 145<li> <a href="is_straight_line_drawing.html"><tt>is_straight_line_drawing</tt> 146</a> 147</ul> 148 149<br> 150<HR> 151Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com"> 152aaron.windsor@gmail.com</a>) 153</BODY> 154</HTML> 155
