| <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: Boyer-Myrvold Planarity Testing/Embedding</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>Boyer-Myrvold Planarity Testing/Embedding</H1> |
| |
| <p> |
| A graph is <a href="./planar_graphs.html#planar"><i>planar</i></a> if it can |
| be drawn in two-dimensional space without any of its edges crossing. Such a |
| drawing of a planar graph is called a |
| <a href="./planar_graphs.html#plane_drawing"><i>plane drawing</i></a>. Each |
| plane drawing belongs to an equivalence class called a <i>planar embedding</i> |
| <a href="#1">[1]</a> that is defined by the clockwise ordering of adjacent |
| edges around each vertex in the graph. A planar embedding is a convenient |
| intermediate representation of an actual drawing of a planar graph, and many |
| planar graph drawing algorithms are formulated as functions mapping a planar |
| embedding to a plane drawing. |
| <br> |
| <br> |
| <table align="center" class="image"> |
| <caption align="bottom"><h5>A planar graph (top left), along with a planar |
| embedding of that graph (bottom left) can be used to create a plane drawing |
| (right) by embedding edges around each vertex in the order in which they |
| appear in the planar embedding. |
| </h5></caption> |
| <tr><td> |
| <img src="./figs/embedding_illustration.png"> |
| </td></tr> |
| <tr></tr> |
| <tr></tr> |
| </table> |
| <br> |
| <p> |
| The function <tt>boyer_myrvold_planarity_test</tt> implements the planarity |
| testing/embedding algorithm of Boyer and Myrvold |
| [<a href="./bibliography.html#boyermyrvold04">70</a>]. |
| <tt>boyer_myrvold_planarity_test</tt> returns <tt>true</tt> if the input graph |
| is planar and <tt>false</tt> otherwise. As a side-effect of this test, a planar |
| embedding can be constructed if the graph is planar or a minimal set of edges |
| that form a <a href = "./planar_graphs.html#kuratowskisubgraphs">Kuratowski |
| subgraph</a> can be found if the graph is not planar. |
| <tt>boyer_myrvold_planarity_test</tt> uses named parameter arguments (courtesy |
| of the <a href="../../parameter/doc/html/index.html">Boost.Parameter</a> |
| library) to specify what the function actually does. Some examples are: |
| |
| <ul> |
| <li>Testing whether or not a graph is planar: |
| <pre> |
| bool is_planar = boyer_myrvold_planarity_test(g); |
| </pre> |
| |
| <li>Computing a planar embedding for a graph if it is planar, otherwise finding |
| a set of edges that forms an obstructing Kuratowski subgraph: |
| <pre> |
| if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, |
| boyer_myrvold_params::embedding = embedding_pmap, |
| boyer_myrvold_params::kuratowski_subgraph = out_itr |
| ) |
| ) |
| { |
| //do something with the embedding in embedding_pmap |
| } |
| else |
| { |
| //do something with the kuratowski subgraph output to out_itr |
| } |
| </pre> |
| </ul> |
| |
| <p> |
| The parameters passed to <tt>boyer_myrvold_planarity_test</tt> in the examples |
| above do more than just carry the data structures used for input and output - |
| the algorithm is optimized at compile time based on which parameters are |
| present. A complete list of parameters accepted and their interactions are |
| described below. |
| <p> |
| <tt>boyer_myrvold_planarity_test</tt> accepts as input any undirected graph, |
| even those with self-loops and multiple edges. |
| However, many planar graph drawing algorithms make additional restrictions |
| on the structure of the input graph - for example, requiring that the input |
| graph is connected, biconnected, or even maximal planar (triangulated.) |
| Fortunately, any planar graph on <i>n</i> vertices that lacks one of these |
| properties can be augmented with additional edges so that it satisfies that |
| property in <i>O(n)</i> time - the functions |
| <tt><a href="./make_connected.html">make_connected</a></tt>, |
| <tt><a href="./make_biconnected_planar.html">make_biconnected_planar</a></tt>, |
| and <tt><a href="./make_maximal_planar.html">make_maximal_planar</a></tt> |
| exist for this purpose. If the graph drawing algorithm you're using requires, |
| say, a biconnected graph, then you must make your input graph biconnected |
| <i>before</i> passing it into <tt>boyer_myrvold_planarity_test</tt> so that the |
| computed planar embedding includes these additional edges. This may require |
| more than one call to <tt>boyer_myrvold_planarity_test</tt> depending on the |
| structure of the graph you begin with, since both |
| <tt>make_biconnected_planar</tt> and <tt>make_maximal_planar</tt> require a |
| planar embedding of the existing graph as an input parameter. |
| |
| <p><p> |
| The named parameters accepted by <tt>boyer_myrvold_planarity_test</tt> are: |
| |
| <ul> |
| <li><b><tt>graph</tt></b> : The input graph - this is the only required |
| parameter. |
| <li><b><tt>vertex_index_map</tt></b> : A mapping from vertices of the input |
| graph to indexes in the range <tt>[0..num_vertices(g))</tt>. If this parameter |
| is not provided, the vertex index map is assumed to be available as an interior |
| property of the graph, accessible by calling <tt>get(vertex_index, g)</tt>. |
| <li><b><tt>edge_index_map</tt></b>: A mapping from the edges of the input graph |
| to indexes in the range <tt>[0..num_edges(g))</tt>. This parameter is only |
| needed if the <tt>kuratowski_subgraph</tt> argument is provided. If the |
| <tt>kuratowski_subgraph</tt> argument is provided and this parameter is not |
| provided, the EdgeIndexMap is assumed to be available as an interior property |
| accessible by calling <tt>get(edge_index, g)</tt>. |
| <li><b><tt>embedding</tt></b> : If the graph is planar, this will be populated |
| with a mapping from vertices to the clockwise order of neighbors in the planar |
| embedding. |
| <li><b><tt>kuratowski_subgraph</tt></b> : If the graph is not planar, a minimal |
| set of edges that form the obstructing Kuratowski subgraph will be written to |
| this iterator. |
| </ul> |
| |
| These named parameters all belong to the namespace |
| <tt>boyer_myrvold_params</tt>. See below for more information on the concepts |
| required for these arguments. |
| |
| <H3>Verifying the output</H3> |
| |
| Whether or not the input graph is planar, <tt>boyer_myrvold_planarity_test</tt> |
| can produce a certificate that can be automatically checked to verify that the |
| function is working properly. |
| <p> |
| If the graph is planar, a planar embedding can be produced. The |
| planar embedding can be verified by passing it to a plane drawing routine |
| (such as <tt><a href="straight_line_drawing.html"> |
| chrobak_payne_straight_line_drawing</a></tt>) and using the function |
| <tt><a href="is_straight_line_drawing.html">is_straight_line_drawing</a></tt> |
| to verify that the resulting graph is planar. |
| <p> |
| If the graph is not planar, a set of edges that forms a Kuratowski subgraph in |
| the original graph can be produced. This set of edges can be passed to the |
| function <tt><a href="is_kuratowski_subgraph.html">is_kuratowski_subgraph</a> |
| </tt> to verify that they can be contracted into a <i>K<sub>5</sub></i> or |
| <i>K<sub>3,3</sub></i>. <tt>boyer_myrvold_planarity_test</tt> chooses the set |
| of edges forming the Kuratowski subgraph in such a way that the contraction to |
| a <i>K<sub>5</sub></i> or <i>K<sub>3,3</sub></i> can be done by a simple |
| deterministic process which is described in the documentation to |
| <tt>is_kuratowski_subgraph</tt>. |
| |
| <H3>Where Defined</H3> |
| |
| <P> |
| <a href="../../../boost/graph/boyer_myrvold_planar_test.hpp"> |
| <TT>boost/graph/boyer_myrvold_planar_test.hpp</TT> |
| </a> |
| |
| <H3>Parameters</H3> |
| |
| IN: <tt>Graph& g</tt> |
| |
| <blockquote> |
| Any undirected graph. The graph type must be a model of |
| <a href="VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a> and |
| <a href="IncidenceGraph.html">IncidenceGraph</a>. |
| </blockquote> |
| |
| OUT <tt>PlanarEmbedding embedding</tt> |
| |
| <blockquote> |
| Must model the <a href="PlanarEmbedding.html">PlanarEmbedding</a> concept. |
| </blockquote> |
| |
| IN <tt>OutputIterator kuratowski_subgraph</tt> |
| |
| <blockquote> |
| An OutputIterator which accepts values of the type |
| <tt>graph_traits<Graph>::edge_descriptor</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> |
| |
| IN <tt>EdgeIndexMap em</tt> |
| |
| <blockquote> |
| A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map |
| </a> that maps edges from <tt>g</tt> to distinct integers in the range |
| <tt>[0, num_edges(g) )</tt><br> |
| <b>Default</b>: <tt>get(edge_index,g)</tt>, but this parameter is only used if |
| the <tt>kuratowski_subgraph_iterator</tt> is provided.<br> |
| </blockquote> |
| |
| <H3>Complexity</H3> |
| |
| Assuming that both the vertex index and edge index supplied take time |
| <i>O(1)</i> to return an index and there are <i>O(n)</i> |
| total self-loops and parallel edges in the graph, most combinations of |
| arguments given to |
| <tt>boyer_myrvold_planarity_test</tt> result in an algorithm that runs in time |
| <i>O(n)</i> for a graph with <i>n</i> vertices and <i>m</i> edges. The only |
| exception is when Kuratowski subgraph isolation is requested for a dense graph |
| (a graph with <i>n = o(m)</i>) - the running time will be <i>O(n+m)</i> |
| <a href = "#2">[2]</a>. |
| |
| <H3>Examples</H3> |
| |
| <P> |
| <ul> |
| <li><a href="../example/simple_planarity_test.cpp">A simple planarity test</a> |
| <li><a href="../example/kuratowski_subgraph.cpp">Isolating a Kuratowski |
| Subgraph</a> |
| <li><a href="../example/straight_line_drawing.cpp">Using a planar embedding to |
| create a straight line drawing</a> |
| </ul> |
| |
| <h3>See Also</h3> |
| |
| <a href="./planar_graphs.html">Planar Graphs in the Boost Graph Library</a> |
| |
| |
| <h3>Notes</h3> |
| |
| <p><a name="1">[1] A planar embedding is also called a <i>combinatorial |
| embedding</i>. |
| |
| <p><a name="2">[2] The algorithm can still be made to run in time <i>O(n)</i> |
| for this case, if needed. <a href="planar_graphs.html#EulersFormula">Euler's |
| formula</a> implies that a planar graph with <i>n</i> vertices can have no more |
| than <i>3n - 6</i> edges, which means that any non-planar graph on <i>n</i> |
| vertices has a subgraph of only <i>3n - 5</i> edges that contains a Kuratowski |
| subgraph. So, if you need to find a Kuratowski subgraph of a graph with more |
| than <i>3n - 5</i> edges in time <i>O(n)</i>, you can create a subgraph of the |
| original graph consisting of any arbitrary <i>3n - 5</i> edges and pass that |
| graph to <tt>boyer_myrvold_planarity_test</tt>. |
| |
| |
| <br> |
| <HR> |
| Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com"> |
| aaron.windsor@gmail.com</a>) |
| </BODY> |
| </HTML> |
