On Point-sets that Support Planar Graphs
Identifieur interne : 001B59 ( Hal/Checkpoint ); précédent : 001B58; suivant : 001B60On Point-sets that Support Planar Graphs
Auteurs : Vida Dujmovi [Canada] ; Will Evans [Canada] ; Sylvain Lazard [France] ; William Lenhart [États-Unis] ; Giuseppe Liotta [Italie] ; David Rappaport [Canada] ; Steve Wismath [Canada]Source :
Abstract
A universal point-set supports a crossing-free drawing of any planar graph. For a planar graph with $n$ vertices, if bends on edges of the drawing are permitted, universal point-sets of size $n$ are known, but only if the bend-points are in arbitrary positions. If the locations of the bend-points must also be specified as part of the point-set, we prove that any planar graph with $n$ vertices can be drawn on a universal set $\cal S$ of $O(n^2/\log n)$ points with at most one bend per edge and with the vertices and the bend points in $\cal S$. If two bends per edge are allowed, we show that $O(n\log n)$ points are sufficient, and if three bends per edge are allowed, $\Theta(n)$ points are sufficient. When no bends on edges are permitted, no universal point-set of size $o(n^2)$ is known for the class of planar graphs. We show that a set of $n$ points in balanced biconvex position supports the class of maximum degree 3 series-parallel lattices.
Url:
Links toward previous steps (curation, corpus...)
Links to Exploration step
Hal:hal-00643824Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">On Point-sets that Support Planar Graphs</title><author><name sortKey="Dujmovi, Vida" sort="Dujmovi, Vida" uniqKey="Dujmovi V" first="Vida" last="Dujmovi">Vida Dujmovi</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-14804" status="VALID"><orgName>School of computer science [Ottawa]</orgName><orgName type="acronym">SCS</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Evans, Will" sort="Evans, Will" uniqKey="Evans W" first="Will" last="Evans">Will Evans</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-48166" status="VALID"><orgName>Computer Science Department</orgName><orgName type="acronym">UBC-Computer Science</orgName><desc><address><addrLine>UBC DEPARTMENT OF COMPUTER SCIENCE ICICS/CS Building 201-2366 Main Mall Vancouver, B.C. V6T 1Z4 General Enquiries: Tel: 604-822-3061 E-mail: info@cs.ubc.ca Fax: 604-822-5485</addrLine><country key="CA"></country></address><ref type="url">http://www.cs.ubc.ca/</ref></desc><listRelation><relation active="#struct-366034" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-366034" type="direct"><org type="institution" xml:id="struct-366034" status="VALID"><orgName>University of British Columbia</orgName><desc><address><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2573" status="OLD"><idno type="RNSR">200518305E</idno><orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName><orgName type="acronym">VEGAS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/vegas</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Lenhart, William" sort="Lenhart, William" uniqKey="Lenhart W" first="William" last="Lenhart">William Lenhart</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-21467" status="VALID"><orgName>Computer Science Department [Williamstown MA]</orgName><desc><address><addrLine>47 Lab Campus Drive Williams College Williamstown, MA 01267</addrLine><country key="US"></country></address><ref type="url">http://www.cs.williams.edu/</ref></desc><listRelation><relation active="#struct-365284" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-365284" type="direct"><org type="institution" xml:id="struct-365284" status="VALID"><orgName>Williams College [Williamstown]</orgName><desc><address><addrLine>Williams College, 18 Hoxsey Street, Williamstown, MA 01267, USA</addrLine><country key="US"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>États-Unis</country></affiliation></author><author><name sortKey="Liotta, Giuseppe" sort="Liotta, Giuseppe" uniqKey="Liotta G" first="Giuseppe" last="Liotta">Giuseppe Liotta</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-74407" status="VALID"><orgName>School of Computing</orgName><desc><address><country key="IT"></country></address></desc><listRelation><relation active="#struct-314094" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-314094" type="direct"><org type="institution" xml:id="struct-314094" status="INCOMING"><orgName>University of Perugia</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Italie</country></affiliation></author><author><name sortKey="Rappaport, David" sort="Rappaport, David" uniqKey="Rappaport D" first="David" last="Rappaport">David Rappaport</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-116025" status="VALID"><orgName>Department of Electrical and Computer Engineering [Queen's University Kingston]</orgName><desc><address><addrLine>19 Union Street, Walter Light Hall, Rm. 416 Queen's University Kingston, Ontario, Canada, K7L 3N6</addrLine><country key="CA"></country></address><ref type="url">http://www.ece.queensu.ca/</ref></desc><listRelation><relation active="#struct-300680" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300680" type="direct"><org type="institution" xml:id="struct-300680" status="VALID"><orgName>Queen's University</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Wismath, Steve" sort="Wismath, Steve" uniqKey="Wismath S" first="Steve" last="Wismath">Steve Wismath</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-7216" status="VALID"><orgName>Department of Mathematics and Computer Science</orgName><desc><address><addrLine>4401 University Drive Lethbridge, Alberta, Canada T1K 3M4</addrLine><country key="CA"></country></address><ref type="url">http://www.uleth.ca/fas/mcs/</ref></desc><listRelation><relation active="#struct-364773" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-364773" type="direct"><org type="institution" xml:id="struct-364773" status="INCOMING"><orgName>UNIVERSITY OF LETHBRIDGE</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-00643824</idno><idno type="halId">hal-00643824</idno><idno type="halUri">https://hal.inria.fr/hal-00643824</idno><idno type="url">https://hal.inria.fr/hal-00643824</idno><date when="2011-09-21">2011-09-21</date><idno type="wicri:Area/Hal/Corpus">003691</idno><idno type="wicri:Area/Hal/Curation">003691</idno><idno type="wicri:Area/Hal/Checkpoint">001B59</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001B59</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">On Point-sets that Support Planar Graphs</title><author><name sortKey="Dujmovi, Vida" sort="Dujmovi, Vida" uniqKey="Dujmovi V" first="Vida" last="Dujmovi">Vida Dujmovi</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-14804" status="VALID"><orgName>School of computer science [Ottawa]</orgName><orgName type="acronym">SCS</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Evans, Will" sort="Evans, Will" uniqKey="Evans W" first="Will" last="Evans">Will Evans</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-48166" status="VALID"><orgName>Computer Science Department</orgName><orgName type="acronym">UBC-Computer Science</orgName><desc><address><addrLine>UBC DEPARTMENT OF COMPUTER SCIENCE ICICS/CS Building 201-2366 Main Mall Vancouver, B.C. V6T 1Z4 General Enquiries: Tel: 604-822-3061 E-mail: info@cs.ubc.ca Fax: 604-822-5485</addrLine><country key="CA"></country></address><ref type="url">http://www.cs.ubc.ca/</ref></desc><listRelation><relation active="#struct-366034" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-366034" type="direct"><org type="institution" xml:id="struct-366034" status="VALID"><orgName>University of British Columbia</orgName><desc><address><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2573" status="OLD"><idno type="RNSR">200518305E</idno><orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName><orgName type="acronym">VEGAS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/vegas</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Lenhart, William" sort="Lenhart, William" uniqKey="Lenhart W" first="William" last="Lenhart">William Lenhart</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-21467" status="VALID"><orgName>Computer Science Department [Williamstown MA]</orgName><desc><address><addrLine>47 Lab Campus Drive Williams College Williamstown, MA 01267</addrLine><country key="US"></country></address><ref type="url">http://www.cs.williams.edu/</ref></desc><listRelation><relation active="#struct-365284" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-365284" type="direct"><org type="institution" xml:id="struct-365284" status="VALID"><orgName>Williams College [Williamstown]</orgName><desc><address><addrLine>Williams College, 18 Hoxsey Street, Williamstown, MA 01267, USA</addrLine><country key="US"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>États-Unis</country></affiliation></author><author><name sortKey="Liotta, Giuseppe" sort="Liotta, Giuseppe" uniqKey="Liotta G" first="Giuseppe" last="Liotta">Giuseppe Liotta</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-74407" status="VALID"><orgName>School of Computing</orgName><desc><address><country key="IT"></country></address></desc><listRelation><relation active="#struct-314094" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-314094" type="direct"><org type="institution" xml:id="struct-314094" status="INCOMING"><orgName>University of Perugia</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Italie</country></affiliation></author><author><name sortKey="Rappaport, David" sort="Rappaport, David" uniqKey="Rappaport D" first="David" last="Rappaport">David Rappaport</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-116025" status="VALID"><orgName>Department of Electrical and Computer Engineering [Queen's University Kingston]</orgName><desc><address><addrLine>19 Union Street, Walter Light Hall, Rm. 416 Queen's University Kingston, Ontario, Canada, K7L 3N6</addrLine><country key="CA"></country></address><ref type="url">http://www.ece.queensu.ca/</ref></desc><listRelation><relation active="#struct-300680" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300680" type="direct"><org type="institution" xml:id="struct-300680" status="VALID"><orgName>Queen's University</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Wismath, Steve" sort="Wismath, Steve" uniqKey="Wismath S" first="Steve" last="Wismath">Steve Wismath</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-7216" status="VALID"><orgName>Department of Mathematics and Computer Science</orgName><desc><address><addrLine>4401 University Drive Lethbridge, Alberta, Canada T1K 3M4</addrLine><country key="CA"></country></address><ref type="url">http://www.uleth.ca/fas/mcs/</ref></desc><listRelation><relation active="#struct-364773" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-364773" type="direct"><org type="institution" xml:id="struct-364773" status="INCOMING"><orgName>UNIVERSITY OF LETHBRIDGE</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">A universal point-set supports a crossing-free drawing of any planar graph. For a planar graph with $n$ vertices, if bends on edges of the drawing are permitted, universal point-sets of size $n$ are known, but only if the bend-points are in arbitrary positions. If the locations of the bend-points must also be specified as part of the point-set, we prove that any planar graph with $n$ vertices can be drawn on a universal set $\cal S$ of $O(n^2/\log n)$ points with at most one bend per edge and with the vertices and the bend points in $\cal S$. If two bends per edge are allowed, we show that $O(n\log n)$ points are sufficient, and if three bends per edge are allowed, $\Theta(n)$ points are sufficient. When no bends on edges are permitted, no universal point-set of size $o(n^2)$ is known for the class of planar graphs. We show that a set of $n$ points in balanced biconvex position supports the class of maximum degree 3 series-parallel lattices.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">On Point-sets that Support Planar Graphs</title><author role="aut"><persName><forename type="first">Vida</forename><surname>Dujmović</surname></persName><email></email><idno type="halauthor">661541</idno><orgName ref="#struct-208909"></orgName><affiliation ref="#struct-14804"></affiliation></author><author role="aut"><persName><forename type="first">Will</forename><surname>Evans</surname></persName><email></email><idno type="halauthor">661542</idno><affiliation ref="#struct-48166"></affiliation></author><author role="aut"><persName><forename type="first">Sylvain</forename><surname>Lazard</surname></persName><email>sylvain.lazard@inria.fr</email><ptr type="url" target="http://www.loria.fr/~lazard/"></ptr><idno type="idhal">sylvain-lazard</idno><idno type="halauthor">661543</idno><affiliation ref="#struct-2573"></affiliation></author><author role="aut"><persName><forename type="first">William</forename><surname>Lenhart</surname></persName><email></email><idno type="halauthor">661544</idno><orgName ref="#struct-365284"></orgName><affiliation ref="#struct-21467"></affiliation></author><author role="aut"><persName><forename type="first">Giuseppe</forename><surname>Liotta</surname></persName><email></email><idno type="halauthor">661545</idno><orgName ref="#struct-368329"></orgName><affiliation ref="#struct-74407"></affiliation></author><author role="aut"><persName><forename type="first">David</forename><surname>Rappaport</surname></persName><email></email><idno type="halauthor">661546</idno><affiliation ref="#struct-116025"></affiliation></author><author role="aut"><persName><forename type="first">Steve</forename><surname>Wismath</surname></persName><email></email><idno type="halauthor">130728</idno><orgName ref="#struct-364773"></orgName><affiliation ref="#struct-7216"></affiliation></author><editor role="depositor"><persName><forename>Sylvain</forename><surname>Lazard</surname></persName><email>sylvain.lazard@inria.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2011-11-22 19:39:00</date><date type="whenModified">2016-05-18 08:55:23</date><date type="whenReleased">2011-11-23 08:58:46</date><date type="whenProduced">2011-09-21</date><date type="whenEndEmbargoed">2011-11-22</date><ref type="file" target="https://hal.inria.fr/hal-00643824/document"><date notBefore="2011-11-22"></date></ref><ref type="file" subtype="author" n="1" target="https://hal.inria.fr/hal-00643824/file/gdproceedings.pdf"><date notBefore="2011-11-22"></date></ref></edition><respStmt><resp>contributor</resp><name key="103314"><persName><forename>Sylvain</forename><surname>Lazard</surname></persName><email>sylvain.lazard@inria.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">hal-00643824</idno><idno type="halUri">https://hal.inria.fr/hal-00643824</idno><idno type="halBibtex">dujmovi:hal-00643824</idno><idno type="halRefHtml">19th International Symposium on Graph Drawing, Sep 2011, Eindhoven, Netherlands. 2011</idno><idno type="halRef">19th International Symposium on Graph Drawing, Sep 2011, Eindhoven, Netherlands. 2011</idno></publicationStmt><seriesStmt><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="LORIA-ACGI" p="LORIA">Algorithmique, calcul, image et géométrie</idno><idno type="stamp" n="INRIA2">INRIA 2</idno><idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno></seriesStmt><notesStmt><note type="audience" n="2">International</note><note type="invited" n="0">No</note><note type="popular" n="0">No</note><note type="peer" n="1">Yes</note><note type="proceedings" n="1">Yes</note></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">On Point-sets that Support Planar Graphs</title><author role="aut"><persName><forename type="first">Vida</forename><surname>Dujmović</surname></persName><idno type="halAuthorId">661541</idno><orgName ref="#struct-208909"></orgName><affiliation ref="#struct-14804"></affiliation></author><author role="aut"><persName><forename type="first">Will</forename><surname>Evans</surname></persName><idno type="halAuthorId">661542</idno><affiliation ref="#struct-48166"></affiliation></author><author role="aut"><persName><forename type="first">Sylvain</forename><surname>Lazard</surname></persName><email>sylvain.lazard@inria.fr</email><ptr type="url" target="http://www.loria.fr/~lazard/"></ptr><idno type="idHal">sylvain-lazard</idno><idno type="halAuthorId">661543</idno><affiliation ref="#struct-2573"></affiliation></author><author role="aut"><persName><forename type="first">William</forename><surname>Lenhart</surname></persName><idno type="halAuthorId">661544</idno><orgName ref="#struct-365284"></orgName><affiliation ref="#struct-21467"></affiliation></author><author role="aut"><persName><forename type="first">Giuseppe</forename><surname>Liotta</surname></persName><idno type="halAuthorId">661545</idno><orgName ref="#struct-368329"></orgName><affiliation ref="#struct-74407"></affiliation></author><author role="aut"><persName><forename type="first">David</forename><surname>Rappaport</surname></persName><idno type="halAuthorId">661546</idno><affiliation ref="#struct-116025"></affiliation></author><author role="aut"><persName><forename type="first">Steve</forename><surname>Wismath</surname></persName><idno type="halAuthorId">130728</idno><orgName ref="#struct-364773"></orgName><affiliation ref="#struct-7216"></affiliation></author></analytic><monogr><meeting><title>19th International Symposium on Graph Drawing</title><date type="start">2011-09-21</date><date type="end">2011-09-23</date><settlement>Eindhoven</settlement><country key="NL">Netherlands</country></meeting><imprint><date type="datePub">2011</date></imprint></monogr></biblStruct></sourceDesc><profileDesc><langUsage><language ident="en">English</language></langUsage><textClass><classCode scheme="halDomain" n="info.info-cg">Computer Science [cs]/Computational Geometry [cs.CG]</classCode><classCode scheme="halTypology" n="COMM">Conference papers</classCode></textClass><abstract xml:lang="en">A universal point-set supports a crossing-free drawing of any planar graph. For a planar graph with $n$ vertices, if bends on edges of the drawing are permitted, universal point-sets of size $n$ are known, but only if the bend-points are in arbitrary positions. If the locations of the bend-points must also be specified as part of the point-set, we prove that any planar graph with $n$ vertices can be drawn on a universal set $\cal S$ of $O(n^2/\log n)$ points with at most one bend per edge and with the vertices and the bend points in $\cal S$. If two bends per edge are allowed, we show that $O(n\log n)$ points are sufficient, and if three bends per edge are allowed, $\Theta(n)$ points are sufficient. When no bends on edges are permitted, no universal point-set of size $o(n^2)$ is known for the class of planar graphs. We show that a set of $n$ points in balanced biconvex position supports the class of maximum degree 3 series-parallel lattices.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001B59 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Checkpoint/biblio.hfd -nk 001B59 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Checkpoint
|type= RBID
|clé= Hal:hal-00643824
|texte= On Point-sets that Support Planar Graphs
}}
| This area was generated with Dilib version V0.6.33. |  |