[ceph.git] / ceph / src / boost / libs / graph / doc / planar_graphs.html

<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: Planar Graphs</TITLE>
</HEAD>
<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>Planar Graphs</H1>

<p>
A graph is <a name="planar"><i>planar</i></a> if it can be drawn in 
two-dimensional space with no two of its edges crossing. Such a drawing of a 
planar graph is called a <a name="plane_drawing"><i>plane drawing</i></a>. 
Every planar graph also admits a <i>straight-line drawing</i>, which is a 
plane drawing where each edge is represented by a line segment. 

<br>
<br>
<table class="image" align="center">
<caption align="bottom">
<h5>A planar graph (left), a plane drawing (center), and a straight line 
drawing (right), all of the same graph</h5>
</caption>
<tr>
<td>
<img src="./figs/planar_plane_straight_line.png">
</td>
</tr>
<tr></tr>
<table>
<br>

Two examples of non-planar graphs are K<sub>5</sub>, the complete graph on 
five vertices, and K<sub>3,3</sub>, the complete bipartite graph on six 
vertices with three vertices in each bipartition. No matter how the vertices 
of either graph are arranged in the plane, at least two edges are forced to 
cross.

<a name = "kuratowskisubgraphs">
<br>
<br>
<table class="image" align="center">
<caption align="bottom"><h5>K<sub>5</sub> (left) and K<sub>3,3</sub> (right) - 
the two Kuratowski subgraphs</h5>
</caption>
<tr>
<td>
<img src="./figs/k_5_and_k_3_3.png">
</td>
</tr>
</table>
<br>

The above graphs are both minimal examples of non-planarity within
their class of graphs; delete any edge or vertex from either one and the 
resulting graph is planar. A theorem of Kuratowski singles these two graphs 
out as fundamental obstructions to planarity within any graph: 
<blockquote>
<i>
A graph is planar if and only if it does not contain a subgraph that is an 
expansion<a href="#1">[1]</a> of either K<sub>5</sub> or K<sub>3,3</sub>
</i>
</blockquote>

<p>
A subgraph that is an expansion of K<sub>5</sub> or K<sub>3,3</sub> is called 
a <a name = "kuratowski_subgraph"><i>Kuratowski subgraph</i></a>. Because of 
the above theorem, given any graph, one can produce either a plane drawing of 
a graph, which will certify that the graph is planar, or a minimal set of edges
that forms a Kuratowski subgraph, which will certify that the graph is 
non-planar - in both cases, the certificate of planarity or non-planarity is 
easy to check.
<p>
Any plane drawing separates the plane into distinct regions bordered by graph 
edges called <i>faces</i>. As a simple example, any embedding of a triangle 
into the plane separates it into two faces: the region inside the triangle and 
the (unbounded) region outside the triangle. The unbounded region outside the 
graph's embedding is called the <i>outer face</i>. Every embedding yields
one outer face and zero or more inner faces. A famous result called 
Euler's formula states that for any 
planar graph with <i>n</i> vertices, <i>e</i> edges, <i>f</i> faces, and 
<i>c</i> connected components,
<a name="EulersFormula">
<blockquote>
<i>n + f = e + c + 1</i>
</blockquote>
</a>
This formula implies that any planar graph with no self-loops or parallel edges
has at most <i>3n - 6</i> edges and <i>2n- 4</i> faces. Because of these
bounds, algorithms on planar graphs can run in time <i>O(n)</i> or space
<i>O(n)</i> on an <i>n</i> vertex graph even if they have to traverse all 
edges or faces of the graph.
<p>
A convenient way to separate the actual planarity test from algorithms that
accept a planar graph as input is through an intermediate structure called a 
<i>planar embedding</i>. Instead of specifying the absolute positions of the 
vertices and edges in the plane as a plane drawing would, a planar embedding 
specifies their positions relative to one another. A planar embedding consists 
of a sequence, for each vertex in the graph, of all of the edges incident on 
that vertex in the order in which they are to be drawn around that vertex.
The orderings defined by this sequence
can either represent a clockwise or counter-clockwise iteration through the
neighbors of each vertex, but the orientation must be
consistent across the entire embedding. 
<p>
In the Boost Graph Library, a planar embedding is a model of the 
<a href="./PlanarEmbedding.html">PlanarEmbedding</a> concept. A type that
models PlanarEmbedding can be passed into the planarity test and populated if 
the input graph is planar. All other "back end" planar graph algorithms accept 
this populated PlanarEmbedding as an input. Conceptually, a type that models 
PlanarEmbedding is a <a href="../../property_map/doc/property_map.html">property 
map</a> that maps each vertex to a sequence of edges,
where the sequence of edges has a similar interface to a standard C++ 
container. The sequence of edges each vertex maps to represents the ordering
of edges adjacent to that vertex. This interface is flexible enough to allow 
storage of the planar embedding independent from the graph in, say, a 
<tt>std::vector</tt> of <tt>std::vector</tt>s, or to allow for graph 
implementations that actually store lists of adjacent edges/vertices to 
internally re-arrange their storage to represent the planar embedding.
Currently, only the former approach is supported when using the native graph 
types (<tt>adjacency_list</tt>, <tt>adjacency_matrix</tt>, etc.)
of the Boost Graph Library.

<H3>Tools for working with planar graphs in the Boost Graph Library</h3>

The Boost Graph Library planar graph algorithms all work on undirected graphs.
Some algorithms require certain degrees of connectivity of the input graph,
but all algorithms work on graphs with self-loops and parallel edges.
<p>
The function <tt><a href = "boyer_myrvold.html">boyer_myrvold_planarity_test
</a></tt> can be used to test whether or not a graph is planar, but it can also
produce two important side-effects: in the case the graph is not planar, it can
isolate a Kuratowski subgraph, and in the case the graph is planar, it can 
compute a planar embedding. The Boyer-Myrvold algorithm works on any undirected
 graph.
<p>
An undirected graph is <i>connected</i> if, for any two vertices <i>u</i> and 
<i>v</i>, there's a path from <i>u</i> to <i>v</i>. An undirected graph is 
<i>biconnected</i> if it is connected and it remains connected even if any
single vertex is removed. Finally, a planar graph is 
<i>maximal planar</i> (also called
<i>triangulated</i>) if no additional edge (with the exception of self-loops
and parallel edges) can be added to it without creating 
a non-planar graph. Any maximal planar simple graph on <i>n > 2</i> vertices 
has exactly <i>3n - 6</i> edges and <i>2n - 4</i> faces, a consequence of 
Euler's formula. If a planar graph isn't connected, isn't biconnected, or isn't
maximal planar, there is some set of edges that can be added to the graph to 
make it satisfy any of those three properties while preserving planarity. Many 
planar graph drawing algorithms make at least one of these three assumptions 
about the input graph, so there are functions in the Boost Graph Library that 
can help:
<ul>
<li><tt><a href="make_connected.html">make_connected</a></tt> adds a minimal 
set of edges to an undirected graph to make it connected.
<li><tt><a href="make_biconnected_planar.html">make_biconnected_planar</a></tt>
adds a set of edges to a connected, undirected planar graph to make it 
biconnected while preserving planarity.
<li><tt><a href="make_maximal_planar.html">make_maximal_planar</a></tt> adds a 
set of edges to a biconnected, undirected planar graph to make it maximal 
planar.
</ul>
<p>
Some algorithms involve a traversal of the faces of the graph, and the Boost 
Graph Library has the generic traversal function 
<tt><a href="planar_face_traversal.html">planar_face_traversal</a></tt> for
this purpose. This traversal, like other traversals in the Boost Graph Library,
can be customized by overriding event points in an appropriately defined
<a href="PlanarFaceVisitor.html">visitor class</a>.
<p>
An intermediate step in some drawing algorithms for planar graphs is the 
creation of 
a <i>canonical ordering</i> of the vertices. A canonical ordering is a 
permutation of the vertices of a maximal planar graph. It orders the vertices 
in a way that makes it straightforward to draw the <i>i</i>th vertex once the 
first <i>(i-1)</i> vertices have been drawn - the only edges connecting the
<i>i</i>th vertex to vertices already drawn will be adjacent to a consecutive 
sequence of vertices along the outer face of the partially embedded graph. The 
function 
<tt><a href="planar_canonical_ordering.html">planar_canonical_ordering</a></tt>
will create such an ordering, given a maximal planar graph and a planar 
embedding of that graph.
<p>
A straight line drawing can be created using the function 
<tt>
<a href="straight_line_drawing.html">chrobak_payne_straight_line_drawing</a>,
</tt> which takes a maximal planar graph, a planar embedding of that 
graph, and a canonical ordering as input. The resulting drawing maps all of the
vertices from a graph with <i>n</i> vertices to integer coordinates on a 
<i>(2n-4) x (n-2)</i> grid such that when the edges of the graph are drawn
as line segments connecting vertices, no two edges cross. Self-loops and 
parallel edges are ignored by this algorithm.
<p>
Finally, there are two functions that can be used to verify the results of the 
<tt>boyer_myrvold_planarity_test</tt> and 
<tt>chrobak_payne_straight_line_drawing</tt> functions:
<ul>
<li><tt><a href="is_kuratowski_subgraph.html">is_kuratowski_subgraph</a></tt> 
takes the output of <tt>boyer_myrvold_planarity_test</tt> on a nonplanar graph 
and verifies that it can be contracted into a graph isomorphic to a Kuratowski 
subgraph.
<li><tt><a href="is_straight_line_drawing.html">is_straight_line_drawing</a>
</tt> takes the output of <tt>chrobak_payne_straight_line_drawing</tt> and uses
a planar sweep algorithm to verify that none of the embedded edges intersect.
</ul>

<h3>Complexity</h3>

Most of the algorithms in the Boost Graph Library that deal with planar graphs 
run in time <i>O(n)</i> on an input graph with <i>n</i> vertices. This achieves
a theoretically optimal bound (you must at least iterate over all <i>n</i> 
vertices in order to embed a graph in the plane.) However, some of the work 
that goes into achieving these theoretically optimal time bounds may come at 
the expense of practical performance. For example, since any comparison-based 
sorting algorithm uses at least on the order of <i>n log n</i> comparisons in 
the worst case, any time an algorithm dealing with planar graphs needs to sort,
a bucket sort is used to sort in <i>O(n)</i> time. Also, computing a planar 
embedding of a graph involves maintaining an ordered list of edges around a 
vertex, and this list of edges needs to support an arbitrary sequence of 
concatenations and reversals. A <tt>std::list</tt> can only guarantee 
<i>O(n<sup>2</sup>)</i> for a mixed sequence of <i>n</i> concatenations and 
reversals (since <tt>reverse</tt> is an <i>O(n)</i> operation.) However, our 
implementation achieves <i>O(n)</i> for these operations by using a list data 
structure that implements mixed sequences of concatenations and reversals 
lazily.
<p>
In both of the above cases, it may be preferable to sacrifice the nice 
theoretical upper bound for performance by using the C++ STL. The bucket sort 
allocates and populates a vector of vectors; because of the overhead in
doing so, <tt>std::stable_sort</tt> may actually be faster in some cases. 
The custom list also uses more space than <tt>std::list</tt>, and it's not 
clear that anything other than carefully constructed pathological examples 
could force a <tt>std::list</tt> to use <i>n<sup>2</sup></i> operations within 
the planar embedding algorithm. For these reasons, the macro 
<tt>BOOST_GRAPH_PREFER_STD_LIB</tt> exists, which, when defined, will force 
the planar graph algorithms to use <tt>std::stable_sort</tt> and 
<tt>std::list</tt> in the examples above.
<p>
See the documentation on individual algorithms for more information about 
complexity guarantees.


<h3>Examples</h3>

<ol>
<li><a href="../example/simple_planarity_test.cpp">Testing whether or not a 
graph is planar.</a>
<li><a href="../example/straight_line_drawing.cpp">Creating a straight line 
drawing of a graph in the plane.</a>
</ol>

<h3>Notes</h3>

<p><a name="1">[1]</a> A graph <i>G'</i> is an expansion of a graph <i>G</i> if
<i>G'</i> can be created from <i>G</i> by a series of zero or more <i>edge 
subdivisions</i>: take any edge <i>{x,y}</i> in the graph, remove it, add a new
vertex <i>z</i>, and add the two edges <i>{x,z}</i> and <i>{z,y}</i> to the 
graph. For example, a path of any length is an expansion of a single edge and 
a cycle of any length is an expansion of a triangle.

<br>
<HR>
Copyright &copy; 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
aaron.windsor@gmail.com</a>)
</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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: Planar Graphs</TITLE>
	11	</HEAD>
	12	<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
	13	ALINK="#ff0000">
	14	<IMG SRC="../../../boost.png"
	15	ALT="C++ Boost" width="277" height="86">
	16
	17	<BR Clear>
	18
	19	<H1>Planar Graphs</H1>
	20
	21	<p>
	22	A graph is <a name="planar"><i>planar</i></a> if it can be drawn in
	23	two-dimensional space with no two of its edges crossing. Such a drawing of a
	24	planar graph is called a <a name="plane_drawing"><i>plane drawing</i></a>.
	25	Every planar graph also admits a <i>straight-line drawing</i>, which is a
	26	plane drawing where each edge is represented by a line segment.
	27
	28	<br>
	29	<br>
	30	<table class="image" align="center">
	31	<caption align="bottom">
	32	<h5>A planar graph (left), a plane drawing (center), and a straight line
	33	drawing (right), all of the same graph</h5>
	34	</caption>
	35	<tr>
	36	<td>
	37	<img src="./figs/planar_plane_straight_line.png">
	38	</td>
	39	</tr>
	40	<tr></tr>
	41	<table>
	42	<br>
	43
	44	Two examples of non-planar graphs are K<sub>5</sub>, the complete graph on
	45	five vertices, and K<sub>3,3</sub>, the complete bipartite graph on six
	46	vertices with three vertices in each bipartition. No matter how the vertices
	47	of either graph are arranged in the plane, at least two edges are forced to
	48	cross.
	49
	50	<a name = "kuratowskisubgraphs">
	51	<br>
	52	<br>
	53	<table class="image" align="center">
	54	<caption align="bottom"><h5>K<sub>5</sub> (left) and K<sub>3,3</sub> (right) -
	55	the two Kuratowski subgraphs</h5>
	56	</caption>
	57	<tr>
	58	<td>
	59	<img src="./figs/k_5_and_k_3_3.png">
	60	</td>
	61	</tr>
	62	</table>
	63	<br>
	64
65	The above graphs are both minimal examples of non-planarity within
66	their class of graphs; delete any edge or vertex from either one and the
67	resulting graph is planar. A theorem of Kuratowski singles these two graphs
68	out as fundamental obstructions to planarity within any graph:
69	<blockquote>
70	<i>
71	A graph is planar if and only if it does not contain a subgraph that is an
72	expansion<a href="#1">[1]</a> of either K<sub>5</sub> or K<sub>3,3</sub>
73	</i>
74	</blockquote>
75
76	<p>
77	A subgraph that is an expansion of K<sub>5</sub> or K<sub>3,3</sub> is called
78	a <a name = "kuratowski_subgraph"><i>Kuratowski subgraph</i></a>. Because of
79	the above theorem, given any graph, one can produce either a plane drawing of
80	a graph, which will certify that the graph is planar, or a minimal set of edges
81	that forms a Kuratowski subgraph, which will certify that the graph is
82	non-planar - in both cases, the certificate of planarity or non-planarity is
83	easy to check.
84	<p>
85	Any plane drawing separates the plane into distinct regions bordered by graph
86	edges called <i>faces</i>. As a simple example, any embedding of a triangle
87	into the plane separates it into two faces: the region inside the triangle and
88	the (unbounded) region outside the triangle. The unbounded region outside the
89	graph's embedding is called the <i>outer face</i>. Every embedding yields
90	one outer face and zero or more inner faces. A famous result called
91	Euler's formula states that for any
92	planar graph with <i>n</i> vertices, <i>e</i> edges, <i>f</i> faces, and
93	<i>c</i> connected components,
94	<a name="EulersFormula">
95	<blockquote>
96	<i>n + f = e + c + 1</i>
97	</blockquote>
98	</a>
99	This formula implies that any planar graph with no self-loops or parallel edges
100	has at most <i>3n - 6</i> edges and <i>2n- 4</i> faces. Because of these
101	bounds, algorithms on planar graphs can run in time <i>O(n)</i> or space
102	<i>O(n)</i> on an <i>n</i> vertex graph even if they have to traverse all
103	edges or faces of the graph.
104	<p>
105	A convenient way to separate the actual planarity test from algorithms that
106	accept a planar graph as input is through an intermediate structure called a
107	<i>planar embedding</i>. Instead of specifying the absolute positions of the
108	vertices and edges in the plane as a plane drawing would, a planar embedding
109	specifies their positions relative to one another. A planar embedding consists
110	of a sequence, for each vertex in the graph, of all of the edges incident on
111	that vertex in the order in which they are to be drawn around that vertex.
112	The orderings defined by this sequence
113	can either represent a clockwise or counter-clockwise iteration through the
114	neighbors of each vertex, but the orientation must be
115	consistent across the entire embedding.
116	<p>
117	In the Boost Graph Library, a planar embedding is a model of the
118	<a href="./PlanarEmbedding.html">PlanarEmbedding</a> concept. A type that
119	models PlanarEmbedding can be passed into the planarity test and populated if
120	the input graph is planar. All other "back end" planar graph algorithms accept
121	this populated PlanarEmbedding as an input. Conceptually, a type that models
122	PlanarEmbedding is a <a href="../../property_map/doc/property_map.html">property
123	map</a> that maps each vertex to a sequence of edges,
124	where the sequence of edges has a similar interface to a standard C++
125	container. The sequence of edges each vertex maps to represents the ordering
126	of edges adjacent to that vertex. This interface is flexible enough to allow
127	storage of the planar embedding independent from the graph in, say, a
128	<tt>std::vector</tt> of <tt>std::vector</tt>s, or to allow for graph
129	implementations that actually store lists of adjacent edges/vertices to
130	internally re-arrange their storage to represent the planar embedding.
131	Currently, only the former approach is supported when using the native graph
132	types (<tt>adjacency_list</tt>, <tt>adjacency_matrix</tt>, etc.)
133	of the Boost Graph Library.
134
135	<H3>Tools for working with planar graphs in the Boost Graph Library</h3>
136
137	The Boost Graph Library planar graph algorithms all work on undirected graphs.
138	Some algorithms require certain degrees of connectivity of the input graph,
139	but all algorithms work on graphs with self-loops and parallel edges.
140	<p>
141	The function <tt><a href = "boyer_myrvold.html">boyer_myrvold_planarity_test
142	</a></tt> can be used to test whether or not a graph is planar, but it can also
143	produce two important side-effects: in the case the graph is not planar, it can
144	isolate a Kuratowski subgraph, and in the case the graph is planar, it can
145	compute a planar embedding. The Boyer-Myrvold algorithm works on any undirected
146	graph.
147	<p>
148	An undirected graph is <i>connected</i> if, for any two vertices <i>u</i> and
149	<i>v</i>, there's a path from <i>u</i> to <i>v</i>. An undirected graph is
150	<i>biconnected</i> if it is connected and it remains connected even if any
151	single vertex is removed. Finally, a planar graph is
152	<i>maximal planar</i> (also called
153	<i>triangulated</i>) if no additional edge (with the exception of self-loops
154	and parallel edges) can be added to it without creating
155	a non-planar graph. Any maximal planar simple graph on <i>n > 2</i> vertices
156	has exactly <i>3n - 6</i> edges and <i>2n - 4</i> faces, a consequence of
157	Euler's formula. If a planar graph isn't connected, isn't biconnected, or isn't
158	maximal planar, there is some set of edges that can be added to the graph to
159	make it satisfy any of those three properties while preserving planarity. Many
160	planar graph drawing algorithms make at least one of these three assumptions
161	about the input graph, so there are functions in the Boost Graph Library that
162	can help:
163	<ul>
164	<li><tt><a href="make_connected.html">make_connected</a></tt> adds a minimal
165	set of edges to an undirected graph to make it connected.
166	<li><tt><a href="make_biconnected_planar.html">make_biconnected_planar</a></tt>
167	adds a set of edges to a connected, undirected planar graph to make it
168	biconnected while preserving planarity.
169	<li><tt><a href="make_maximal_planar.html">make_maximal_planar</a></tt> adds a
170	set of edges to a biconnected, undirected planar graph to make it maximal
171	planar.
172	</ul>
173	<p>
174	Some algorithms involve a traversal of the faces of the graph, and the Boost
175	Graph Library has the generic traversal function
176	<tt><a href="planar_face_traversal.html">planar_face_traversal</a></tt> for
177	this purpose. This traversal, like other traversals in the Boost Graph Library,
178	can be customized by overriding event points in an appropriately defined
179	<a href="PlanarFaceVisitor.html">visitor class</a>.
180	<p>
181	An intermediate step in some drawing algorithms for planar graphs is the
182	creation of
183	a <i>canonical ordering</i> of the vertices. A canonical ordering is a
184	permutation of the vertices of a maximal planar graph. It orders the vertices
185	in a way that makes it straightforward to draw the <i>i</i>th vertex once the
186	first <i>(i-1)</i> vertices have been drawn - the only edges connecting the
187	<i>i</i>th vertex to vertices already drawn will be adjacent to a consecutive
188	sequence of vertices along the outer face of the partially embedded graph. The
189	function
190	<tt><a href="planar_canonical_ordering.html">planar_canonical_ordering</a></tt>
191	will create such an ordering, given a maximal planar graph and a planar
192	embedding of that graph.
193	<p>
194	A straight line drawing can be created using the function
195	<tt>
196	<a href="straight_line_drawing.html">chrobak_payne_straight_line_drawing</a>,
197	</tt> which takes a maximal planar graph, a planar embedding of that
198	graph, and a canonical ordering as input. The resulting drawing maps all of the
199	vertices from a graph with <i>n</i> vertices to integer coordinates on a
200	<i>(2n-4) x (n-2)</i> grid such that when the edges of the graph are drawn
201	as line segments connecting vertices, no two edges cross. Self-loops and
202	parallel edges are ignored by this algorithm.
203	<p>
204	Finally, there are two functions that can be used to verify the results of the
205	<tt>boyer_myrvold_planarity_test</tt> and
206	<tt>chrobak_payne_straight_line_drawing</tt> functions:
207	<ul>
208	<li><tt><a href="is_kuratowski_subgraph.html">is_kuratowski_subgraph</a></tt>
209	takes the output of <tt>boyer_myrvold_planarity_test</tt> on a nonplanar graph
210	and verifies that it can be contracted into a graph isomorphic to a Kuratowski
211	subgraph.
212	<li><tt><a href="is_straight_line_drawing.html">is_straight_line_drawing</a>
213	</tt> takes the output of <tt>chrobak_payne_straight_line_drawing</tt> and uses
214	a planar sweep algorithm to verify that none of the embedded edges intersect.
215	</ul>
216
217	<h3>Complexity</h3>
218
219	Most of the algorithms in the Boost Graph Library that deal with planar graphs
220	run in time <i>O(n)</i> on an input graph with <i>n</i> vertices. This achieves
221	a theoretically optimal bound (you must at least iterate over all <i>n</i>
222	vertices in order to embed a graph in the plane.) However, some of the work
223	that goes into achieving these theoretically optimal time bounds may come at
224	the expense of practical performance. For example, since any comparison-based
225	sorting algorithm uses at least on the order of <i>n log n</i> comparisons in
226	the worst case, any time an algorithm dealing with planar graphs needs to sort,
227	a bucket sort is used to sort in <i>O(n)</i> time. Also, computing a planar
228	embedding of a graph involves maintaining an ordered list of edges around a
229	vertex, and this list of edges needs to support an arbitrary sequence of
230	concatenations and reversals. A <tt>std::list</tt> can only guarantee
231	<i>O(n<sup>2</sup>)</i> for a mixed sequence of <i>n</i> concatenations and
232	reversals (since <tt>reverse</tt> is an <i>O(n)</i> operation.) However, our
233	implementation achieves <i>O(n)</i> for these operations by using a list data
234	structure that implements mixed sequences of concatenations and reversals
235	lazily.
236	<p>
237	In both of the above cases, it may be preferable to sacrifice the nice
238	theoretical upper bound for performance by using the C++ STL. The bucket sort
239	allocates and populates a vector of vectors; because of the overhead in
240	doing so, <tt>std::stable_sort</tt> may actually be faster in some cases.
241	The custom list also uses more space than <tt>std::list</tt>, and it's not
242	clear that anything other than carefully constructed pathological examples
243	could force a <tt>std::list</tt> to use <i>n<sup>2</sup></i> operations within
244	the planar embedding algorithm. For these reasons, the macro
245	<tt>BOOST_GRAPH_PREFER_STD_LIB</tt> exists, which, when defined, will force
246	the planar graph algorithms to use <tt>std::stable_sort</tt> and
247	<tt>std::list</tt> in the examples above.
248	<p>
249	See the documentation on individual algorithms for more information about
250	complexity guarantees.
251
252
253	<h3>Examples</h3>
254
255	<ol>
256	<li><a href="../example/simple_planarity_test.cpp">Testing whether or not a
257	graph is planar.</a>
258	<li><a href="../example/straight_line_drawing.cpp">Creating a straight line
259	drawing of a graph in the plane.</a>
260	</ol>
261
262	<h3>Notes</h3>
263
264	<p><a name="1">[1]</a> A graph <i>G'</i> is an expansion of a graph <i>G</i> if
265	<i>G'</i> can be created from <i>G</i> by a series of zero or more <i>edge
266	subdivisions</i>: take any edge <i>{x,y}</i> in the graph, remove it, add a new
267	vertex <i>z</i>, and add the two edges <i>{x,z}</i> and <i>{z,y}</i> to the
268	graph. For example, a path of any length is an expansion of a single edge and
269	a cycle of any length is an expansion of a triangle.
270
271	<br>
272	<HR>
273	Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
274	aaron.windsor@gmail.com</a>)
275	</BODY>
276	</HTML>