http://openproblemgarden.org/op/small_universal_point_sets_for_planar_graphs Comments for "Universal point sets for planar graphs" en http://openproblemgarden.org/op/small_universal_point_sets_for_planar_graphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/mohar">Mohar</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/topological_graph_theory">Topological G.T.</a> » <a href="/category/drawings_0">Drawings</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>We say that a set <img class="teximage" src="/files/tex/8d81516c76827abd4181af4edde83aea10aff424.png" alt="$ P \subseteq {\mathbb R}^2 $" /> is <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" />-<em>universal</em> if every <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in <img class="teximage" src="/files/tex/b2b0b759db4d5a1b3204c38cdee6d9bd9e0d0dab.png" alt="$ P $" />, and all edges are (non-intersecting) straight line segments. </p> <div class="envtheorem"><b>Question</b>&nbsp;&nbsp; Does there exist an <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" />-universal set of size <img class="teximage" src="/files/tex/ee18510ab4140627d7a8df7949d309533b39ebca.png" alt="$ O(n) $" />? </div> </tr></td> </table> </td> </tr> </table> Mohar, Bojan geometric graph planar graph universal set Graph Theory Topological Graph Theory Drawings http://openproblemgarden.org/op/small_universal_point_sets_for_planar_graphs#comment Tue, 22 May 2007 06:54:34 +0200 mdevos 326 at http://openproblemgarden.org