boost_1_45_0/libs/graph/doc/planar_graphs.html - nest-learning-thermostat/5.0/boost - Git at Google

 <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>
	<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 © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">
	aaron.windsor@gmail.com</a>)
	</BODY>
	</HTML>