mooigraph
/
regraphlet


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518
							<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
      <title>GTL - Graph Template Library: planarity Class Reference</title>
      <link href="doxygen.css" rel="stylesheet" type="text/css">
  </head>
  <body>
    <p class="links">  
      <a href="../index.html">Home</a> |
      Documentation |
      <a href="../register.html">Download</a> |
      <a href="../platforms.html">Platforms</a> |
      <a href="../refer.html">Projects</a> |      
      <a href="../lists.html">Mailing Lists</a> |
      <a href="../history.html">Version History</a>
    </p>

<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
  <ul>
    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    <li class="current"><a href="classes.html"><span>Classes</span></a></li>
    <li><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<div class="tabs">
  <ul>
    <li><a href="classes.html"><span>Alphabetical&nbsp;List</span></a></li>
    <li><a href="annotated.html"><span>Class&nbsp;List</span></a></li>
    <li><a href="hierarchy.html"><span>Class&nbsp;Hierarchy</span></a></li>
    <li><a href="functions.html"><span>Class&nbsp;Members</span></a></li>
  </ul>
</div>
<h1>planarity Class Reference</h1><!-- doxytag: class="planarity" --><!-- doxytag: inherits="algorithm" -->Tests if a graph can be drawn on a plane without any edge crossings.  
<a href="#_details">More...</a>
<p>
<div class="dynheader">
Inheritance diagram for planarity:</div>
<div class="dynsection">
<p><center><img src="a00188.gif" border="0" usemap="#a00189" alt="Inheritance graph"></center>
<map name="a00189">
<area shape="rect" href="a00001.html" title="Abstract baseclass for all algoritm&#45;classes." alt="" coords="5,7,83,31"></map>
<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center></div>
<div class="dynheader">
Collaboration diagram for planarity:</div>
<div class="dynsection">
<p><center><img src="a00190.gif" border="0" usemap="#a00191" alt="Collaboration graph"></center>
<map name="a00191">
<area shape="rect" href="a00001.html" title="Abstract baseclass for all algoritm&#45;classes." alt="" coords="5,97,83,121"><area shape="rect" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing." alt="" coords="107,97,240,121"><area shape="rect" title="embedding" alt="" coords="156,119,164,127"><area shape="rect" title="embedding" alt="" coords="95,184,103,192"><area shape="rect" href="a00014.html" title="A directed or undirected graph." alt="" coords="145,7,201,31"><area shape="rect" title="G" alt="" coords="169,28,177,36"><area shape="rect" title="G" alt="" coords="169,93,177,101"></map>
<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center></div>

<p>
<a href="a00192.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#a928bc1c8d0c89b6523bc1e7456f4c91">planarity</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Creates an object of the <a class="el" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings.">planarity</a> test algorithm.  <a href="#a928bc1c8d0c89b6523bc1e7456f4c91"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="3e0c0f1a724191042947dfecc640bf05"></a><!-- doxytag: member="planarity::~planarity" ref="3e0c0f1a724191042947dfecc640bf05" args="()" -->
&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#3e0c0f1a724191042947dfecc640bf05">~planarity</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Destructor. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#e06c471d957a116aad14e338c341f8b1">check</a> (<a class="el" href="a00014.html">graph</a> &amp;G)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Checks whether <a class="el" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings.">planarity</a> test can be applied to <code>G</code>.  <a href="#e06c471d957a116aad14e338c341f8b1"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#93232e765c08dd2a4c00d192bb48b5fc">run</a> (<a class="el" href="a00014.html">graph</a> &amp;G)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Runs <a class="el" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings.">planarity</a> test on <code>G</code>.  <a href="#93232e765c08dd2a4c00d192bb48b5fc"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#ca500e3d46a99c6231aff86afa2a71b1">reset</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Resets <a class="el" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> object, such that it can be applied to another <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a>.  <a href="#ca500e3d46a99c6231aff86afa2a71b1"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#1679e285a7135b48b572764f5e8e773d">calc_embedding</a> (bool p)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">If <code>p</code> is true a planar embedding will be calculated in the next run.  <a href="#1679e285a7135b48b572764f5e8e773d"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#7806f9040f6ba20befb15ea3a25ba76a">calc_embedding</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns true if a planar embedding will be calculated in the next run.  <a href="#7806f9040f6ba20befb15ea3a25ba76a"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#7b8e8e5414a4eedb0f99253d3b62ffa3">calc_obstruction</a> (bool p)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">If <code>p</code> is true the obstructions to planarity will be calculated in the next run.  <a href="#7b8e8e5414a4eedb0f99253d3b62ffa3"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#16713450b2930008709b87fc4f32fc6f">calc_obstruction</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns true if the obstructions to planarity will be calculated in the next run.  <a href="#16713450b2930008709b87fc4f32fc6f"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#f67236533dce559d2670eae581750f54">make_biconnected</a> (bool p)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Determines the strategy used to test a <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> which is not biconnected.  <a href="#f67236533dce559d2670eae581750f54"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#ab1a8ac05bacd090cb347340e0f9d119">make_biconnected</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns strategy for testing graphs, which are not biconnected.  <a href="#ab1a8ac05bacd090cb347340e0f9d119"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#7a623f4c0e5c753a01dab6c0a79c3b50">is_planar</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Result of last test.  <a href="#7a623f4c0e5c753a01dab6c0a79c3b50"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00022.html">planar_embedding</a> &amp;&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#9ab79a340e361c3300cc08e82edd4e12">get_embedding</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">If graph in last <a class="el" href="a00023.html#93232e765c08dd2a4c00d192bb48b5fc" title="Runs planarity test on G.">run</a> was planar a planar embedding is calculated during the reductions. This function gives access to it.  <a href="#9ab79a340e361c3300cc08e82edd4e12"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">list&lt; <a class="el" href="a00010.html">edge</a> &gt; &amp;&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#c9021696934cc24afbc36aa307b2919b">get_obstruction_edges</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns the edges of a subgraph homeomorphic to either K3,3 or K5 if graph in last run was not planar.  <a href="#c9021696934cc24afbc36aa307b2919b"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">list&lt; <a class="el" href="a00020.html">node</a> &gt; &amp;&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00023.html#c1bee50e38d398f3868a3308164caa31">get_obstruction_nodes</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns the nodes of a subgraph homeomorphic to either K3,3 or K5 if graph in last run was not planar.  <a href="#c1bee50e38d398f3868a3308164caa31"></a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
Tests if a graph can be drawn on a plane without any edge crossings. 
<p>
<dl class="rcs" compact><dt><b>Date</b></dt><dd></dd></dl>
<dl class="rcs" compact><dt><b>Revision</b></dt><dd></dd></dl>
<p>
This class implements the Lempel-Even-Cederbaum planarity test using PQ-trees. In case the graph is planar a planar embedding is obtained, i.e. for each node in the graph an ordered adjacency list is calculated, such that there exists a planar drawing in which all adjacent edges around a node apply to this order.<p>
If the graph is not planar Kuratowski's famous theorem states that it must contain a subgraph hoemeomorphic to either K5 (the complete graph with five nodes) or K3,3 (the complete bipartite graph with three nodes each side). In this case the nodes and edges of the tested graph that form either of these two are calculated.<p>
In case the graph is planar and has <img class="formulaInl" alt="$N$" src="form_3.png"> nodes the <a class="el" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> needs <img class="formulaInl" alt="$\mathcal{O}(N)$" src="form_4.png"> time for the test (including the planar embedding). In case the graph isn't planar it needs at most <img class="formulaInl" alt="$\mathcal{O}(E)$" src="form_5.png"> time if <img class="formulaInl" alt="$E$" src="form_6.png"> is the number of edges for both the test and the detection of K5 or K3,3. <hr><h2>Constructor &amp; Destructor Documentation</h2>
<a class="anchor" name="a928bc1c8d0c89b6523bc1e7456f4c91"></a><!-- doxytag: member="planarity::planarity" ref="a928bc1c8d0c89b6523bc1e7456f4c91" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">planarity::planarity           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Creates an object of the <a class="el" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings.">planarity</a> test algorithm. 
<p>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> </dd></dl>

</div>
</div><p>
<hr><h2>Member Function Documentation</h2>
<a class="anchor" name="e06c471d957a116aad14e338c341f8b1"></a><!-- doxytag: member="planarity::check" ref="e06c471d957a116aad14e338c341f8b1" args="(graph &amp;G)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int planarity::check           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Checks whether <a class="el" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings.">planarity</a> test can be applied to <code>G</code>. 
<p>
This should return always <code>GTL_OK</code>. There aren't any restrictions on <code>G</code>, even multiple edges and selfloops are tolerated.<p>
<dl class="note" compact><dt><b>Note:</b></dt><dd>Selfloops and multiple edges will not be added to the planar embedding. <a class="el" href="a00022.html#b04859be18352bc53a120b0676a499ba">planar_embedding::selfloops</a> and <a class="el" href="a00022.html#fb50ef8f3b5b2c6690b9d364db21f36f">planar_embedding::multiple_edges</a> can be used to get these.</dd></dl>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>arbitrary graph</td></tr>
  </table>
</dl>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>GTL_OK</em>&nbsp;</td><td>if planarity test can be applied </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>GTL_ERROR</em>&nbsp;</td><td>if not</td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00001.html#76361fb03ad1cf643affc51821e43bed" title="Checks whether all preconditions are satisfied.">algorithm::check</a> </dd></dl>

<p>Implements <a class="el" href="a00001.html#76361fb03ad1cf643affc51821e43bed">algorithm</a>.</p>

</div>
</div><p>
<a class="anchor" name="93232e765c08dd2a4c00d192bb48b5fc"></a><!-- doxytag: member="planarity::run" ref="93232e765c08dd2a4c00d192bb48b5fc" args="(graph &amp;G)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">int planarity::run           </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="a00014.html">graph</a> &amp;&nbsp;</td>
          <td class="paramname"> <em>G</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Runs <a class="el" href="a00023.html" title="Tests if a graph can be drawn on a plane without any edge crossings.">planarity</a> test on <code>G</code>. 
<p>
This should return always <code>GTL_OK</code>. The return value only tracks errors that might occur, it is definitly <em>not</em> the result of the test itself. The result of the test is stored in a member variable and can be accessed via <a class="el" href="a00023.html#7a623f4c0e5c753a01dab6c0a79c3b50" title="Result of last test.">is_planar</a>.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>G</em>&nbsp;</td><td>arbitrary graph</td></tr>
  </table>
</dl>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>GTL_OK</em>&nbsp;</td><td>if planarity test was sucessfully applied </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>GTL_ERROR</em>&nbsp;</td><td>if not</td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca" title="Applies algorithm to graph g.">algorithm::run</a> </dd></dl>

<p>Implements <a class="el" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca">algorithm</a>.</p>

</div>
</div><p>
<a class="anchor" name="ca500e3d46a99c6231aff86afa2a71b1"></a><!-- doxytag: member="planarity::reset" ref="ca500e3d46a99c6231aff86afa2a71b1" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void planarity::reset           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [virtual]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Resets <a class="el" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a> object, such that it can be applied to another <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a>. 
<p>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00001.html#21aba63d066ae7897de6ca7d8425c408" title="Resets algorithm.">algorithm::reset</a> </dd></dl>

<p>Implements <a class="el" href="a00001.html#21aba63d066ae7897de6ca7d8425c408">algorithm</a>.</p>

</div>
</div><p>
<a class="anchor" name="1679e285a7135b48b572764f5e8e773d"></a><!-- doxytag: member="planarity::calc_embedding" ref="1679e285a7135b48b572764f5e8e773d" args="(bool p)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void planarity::calc_embedding           </td>
          <td>(</td>
          <td class="paramtype">bool&nbsp;</td>
          <td class="paramname"> <em>p</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
If <code>p</code> is true a planar embedding will be calculated in the next run. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>p</em>&nbsp;</td><td><code>true</code> iff embedding should be calculated</td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00023.html#9ab79a340e361c3300cc08e82edd4e12" title="If graph in last run was planar a planar embedding is calculated during the reductions...">get_embedding</a> <p>
<a class="el" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="7806f9040f6ba20befb15ea3a25ba76a"></a><!-- doxytag: member="planarity::calc_embedding" ref="7806f9040f6ba20befb15ea3a25ba76a" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool planarity::calc_embedding           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns true if a planar embedding will be calculated in the next run. 
<p>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>iff embedding will be calculated</td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00023.html#9ab79a340e361c3300cc08e82edd4e12" title="If graph in last run was planar a planar embedding is calculated during the reductions...">get_embedding</a> <p>
<a class="el" href="a00022.html" title="Ordered adjacency lists as a result of planarity testing.">planar_embedding</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="7b8e8e5414a4eedb0f99253d3b62ffa3"></a><!-- doxytag: member="planarity::calc_obstruction" ref="7b8e8e5414a4eedb0f99253d3b62ffa3" args="(bool p)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void planarity::calc_obstruction           </td>
          <td>(</td>
          <td class="paramtype">bool&nbsp;</td>
          <td class="paramname"> <em>p</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
If <code>p</code> is true the obstructions to planarity will be calculated in the next run. 
<p>
This implies the calculation of an embedding.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>p</em>&nbsp;</td><td><code>true</code> iff obstructions to planarity should be calculated</td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00023.html#c9021696934cc24afbc36aa307b2919b" title="Returns the edges of a subgraph homeomorphic to either K3,3 or K5 if graph in last...">get_obstruction_edges</a> <p>
<a class="el" href="a00023.html#c1bee50e38d398f3868a3308164caa31" title="Returns the nodes of a subgraph homeomorphic to either K3,3 or K5 if graph in last...">get_obstruction_nodes</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="16713450b2930008709b87fc4f32fc6f"></a><!-- doxytag: member="planarity::calc_obstruction" ref="16713450b2930008709b87fc4f32fc6f" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool planarity::calc_obstruction           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns true if the obstructions to planarity will be calculated in the next run. 
<p>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>iff obstructions to planarity will be calculated</td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00023.html#c9021696934cc24afbc36aa307b2919b" title="Returns the edges of a subgraph homeomorphic to either K3,3 or K5 if graph in last...">get_obstruction_edges</a> <p>
<a class="el" href="a00023.html#c1bee50e38d398f3868a3308164caa31" title="Returns the nodes of a subgraph homeomorphic to either K3,3 or K5 if graph in last...">get_obstruction_nodes</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="f67236533dce559d2670eae581750f54"></a><!-- doxytag: member="planarity::make_biconnected" ref="f67236533dce559d2670eae581750f54" args="(bool p)" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void planarity::make_biconnected           </td>
          <td>(</td>
          <td class="paramtype">bool&nbsp;</td>
          <td class="paramname"> <em>p</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Determines the strategy used to test a <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> which is not biconnected. 
<p>
If this is enabled the <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> will be made biconnected by adding some new edges. This is usually faster than testing the biconnected <a class="el" href="a00007.html" title="Connected components algorithm.">components</a> one by one, which is done if this option is disabled. By default this is enabled.<p>
<dl class="note" compact><dt><b>Note:</b></dt><dd>This is not fully tested, i.e. at the moment this feature should be used only for the test without embedding or kuratowski graphs.</dd></dl>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>p</em>&nbsp;</td><td>true iff graph should be made biconnected</td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00004.html#774fd08203a6d164605afc4cdc8b9201" title="If enabled edges will be added to the graph in order to make it biconnected, if cutpoints...">biconnectivity::make_biconnected</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="ab1a8ac05bacd090cb347340e0f9d119"></a><!-- doxytag: member="planarity::make_biconnected" ref="ab1a8ac05bacd090cb347340e0f9d119" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool planarity::make_biconnected           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns strategy for testing graphs, which are not biconnected. 
<p>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>iff <a class="el" href="a00014.html" title="A directed or undirected graph.">graph</a> will be made biconnected before test</td></tr>
  </table>
</dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00004.html#774fd08203a6d164605afc4cdc8b9201" title="If enabled edges will be added to the graph in order to make it biconnected, if cutpoints...">biconnectivity::make_biconnected</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="7a623f4c0e5c753a01dab6c0a79c3b50"></a><!-- doxytag: member="planarity::is_planar" ref="7a623f4c0e5c753a01dab6c0a79c3b50" args="() const " -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">bool planarity::is_planar           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Result of last test. 
<p>
<dl compact><dt><b>Return values:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>true</em>&nbsp;</td><td>iff graph in last run was planar. </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="9ab79a340e361c3300cc08e82edd4e12"></a><!-- doxytag: member="planarity::get_embedding" ref="9ab79a340e361c3300cc08e82edd4e12" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00022.html">planar_embedding</a>&amp; planarity::get_embedding           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
If graph in last <a class="el" href="a00023.html#93232e765c08dd2a4c00d192bb48b5fc" title="Runs planarity test on G.">run</a> was planar a planar embedding is calculated during the reductions. This function gives access to it. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>planar embedding of graph in last run</dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00023.html#1679e285a7135b48b572764f5e8e773d" title="If p is true a planar embedding will be calculated in the next run.">calc_embedding</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="c9021696934cc24afbc36aa307b2919b"></a><!-- doxytag: member="planarity::get_obstruction_edges" ref="c9021696934cc24afbc36aa307b2919b" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">list&lt;<a class="el" href="a00010.html">edge</a>&gt;&amp; planarity::get_obstruction_edges           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns the edges of a subgraph homeomorphic to either K3,3 or K5 if graph in last run was not planar. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>edges of subgraph homeomorphic to either K3,3 or K5</dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00023.html#c1bee50e38d398f3868a3308164caa31" title="Returns the nodes of a subgraph homeomorphic to either K3,3 or K5 if graph in last...">get_obstruction_nodes</a> <p>
<a class="el" href="a00023.html#7b8e8e5414a4eedb0f99253d3b62ffa3" title="If p is true the obstructions to planarity will be calculated in the next run.">calc_obstruction</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="c1bee50e38d398f3868a3308164caa31"></a><!-- doxytag: member="planarity::get_obstruction_nodes" ref="c1bee50e38d398f3868a3308164caa31" args="()" -->
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">list&lt;<a class="el" href="a00020.html">node</a>&gt;&amp; planarity::get_obstruction_nodes           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns the nodes of a subgraph homeomorphic to either K3,3 or K5 if graph in last run was not planar. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>nodes of subgraph homeomorphic to either K3,3 or K5</dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00023.html#c9021696934cc24afbc36aa307b2919b" title="Returns the edges of a subgraph homeomorphic to either K3,3 or K5 if graph in last...">get_obstruction_edges</a> <p>
<a class="el" href="a00023.html#7b8e8e5414a4eedb0f99253d3b62ffa3" title="If p is true the obstructions to planarity will be calculated in the next run.">calc_obstruction</a> </dd></dl>

</div>
</div><p>
    <p class="links">
      <a href="http://www.uni-passau.de/">University of Passau</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/">FMI</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
	Computer Science</a>
    </p>
  <div class="copyright">
      Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
  </div>
</body>
</html>