InforLorV4, Main, Merge, bibRecord, 002146

On Point-sets that Support Planar Graphs

Identifieur interne : 002146 ( Main/Merge ); précédent : 002145; suivant : 002147

On 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 :

RBID : Hal:hal-00643824

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:

https://hal.inria.fr/hal-00643824

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 003691
to stream Hal, to step Curation: 003691
to stream Hal, to step Checkpoint: 001B59

Links to Exploration step

Hal:hal-00643824

Le 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>
<idno type="wicri:Area/Main/Merge">002146</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>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002146 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 002146 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Merge
   |type=    RBID
   |clé=     Hal:hal-00643824
   |texte=   On Point-sets that Support Planar Graphs
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

On Point-sets that Support Planar Graphs

On Point-sets that Support Planar Graphs

Source :

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri