InforLorV4, Hal, Corpus, bibRecord, 003690

On Point-sets that Support Planar Graphs

Identifieur interne : 003690 ( Hal/Corpus ); précédent : 003689; suivant : 003691

On Point-sets that Support Planar Graphs

Auteurs : Vida Dujmovi ; Will Evans ; Sylvain Lazard ; William Lenhart ; Giuseppe Liotta ; David Rappaport ; Steve Wismath

Source :

Computational Geometry [ 0925-7721 ] ; 2013.

RBID : Hal:hal-00684510

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, $O(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-00684510

DOI: 10.1016/j.comgeo.2012.03.003

Links to Exploration step

Hal:hal-00684510

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><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>
</affiliation>
</author>
<author><name sortKey="Evans, Will" sort="Evans, Will" uniqKey="Evans W" first="Will" last="Evans">Will Evans</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation><hal:affiliation type="researchteam" xml:id="struct-205129" status="VALID"><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-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</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/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</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-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<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 active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</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>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Lenhart, William" sort="Lenhart, William" uniqKey="Lenhart W" first="William" last="Lenhart">William Lenhart</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Liotta, Giuseppe" sort="Liotta, Giuseppe" uniqKey="Liotta G" first="Giuseppe" last="Liotta">Giuseppe Liotta</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Rappaport, David" sort="Rappaport, David" uniqKey="Rappaport D" first="David" last="Rappaport">David Rappaport</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Wismath, Steve" sort="Wismath, Steve" uniqKey="Wismath S" first="Steve" last="Wismath">Steve Wismath</name>
<affiliation><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>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00684510</idno>
<idno type="halId">hal-00684510</idno>
<idno type="halUri">https://hal.inria.fr/hal-00684510</idno>
<idno type="url">https://hal.inria.fr/hal-00684510</idno>
<idno type="doi">10.1016/j.comgeo.2012.03.003</idno>
<date when="2013">2013</date>
<idno type="wicri:Area/Hal/Corpus">003690</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><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>
</affiliation>
</author>
<author><name sortKey="Evans, Will" sort="Evans, Will" uniqKey="Evans W" first="Will" last="Evans">Will Evans</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation><hal:affiliation type="researchteam" xml:id="struct-205129" status="VALID"><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-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</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/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</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-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<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 active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</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>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Lenhart, William" sort="Lenhart, William" uniqKey="Lenhart W" first="William" last="Lenhart">William Lenhart</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Liotta, Giuseppe" sort="Liotta, Giuseppe" uniqKey="Liotta G" first="Giuseppe" last="Liotta">Giuseppe Liotta</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Rappaport, David" sort="Rappaport, David" uniqKey="Rappaport D" first="David" last="Rappaport">David Rappaport</name>
<affiliation><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>
</affiliation>
</author>
<author><name sortKey="Wismath, Steve" sort="Wismath, Steve" uniqKey="Wismath S" first="Steve" last="Wismath">Steve Wismath</name>
<affiliation><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>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1016/j.comgeo.2012.03.003</idno>
<series><title level="j">Computational Geometry</title>
<idno type="ISSN">0925-7721</idno>
<imprint><date type="datePub">2013</date>
</imprint>
</series>
</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, $O(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-205129"></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">2012-04-02 12:17:43</date>
<date type="whenModified">2015-12-16 01:09:37</date>
<date type="whenReleased">2012-04-02 16:33:37</date>
<date type="whenProduced">2013</date>
<date type="whenEndEmbargoed">2012-04-02</date>
<ref type="file" target="https://hal.inria.fr/hal-00684510/document"><date notBefore="2012-04-02"></date>
</ref>
<ref type="file" subtype="author" n="1" target="https://hal.inria.fr/hal-00684510/file/journalversion.pdf"><date notBefore="2012-04-02"></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-00684510</idno>
<idno type="halUri">https://hal.inria.fr/hal-00684510</idno>
<idno type="halBibtex">dujmovi:hal-00684510</idno>
<idno type="halRefHtml">Computational Geometry, Elsevier, 2013, 43 (1), pp.29--50. <10.1016/j.comgeo.2012.03.003></idno>
<idno type="halRef">Computational Geometry, Elsevier, 2013, 43 (1), pp.29--50. <10.1016/j.comgeo.2012.03.003></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="LORIA2">Publications du LORIA</idno>
<idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA-ACGI" p="LORIA">Algorithmique, calcul, image et géométrie</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
<idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="LORIA-ALGO-TEST5">LORIA-ALGO-TEST5  </idno>
<idno type="stamp" n="INRIA2">INRIA 2</idno>
</seriesStmt>
<notesStmt><note type="audience" n="2">International</note>
<note type="popular" n="0">No</note>
<note type="peer" 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-205129"></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><idno type="halJournalId" status="VALID">11999</idno>
<idno type="issn">0925-7721</idno>
<title level="j">Computational Geometry</title>
<imprint><publisher>Elsevier</publisher>
<biblScope unit="volume">43</biblScope>
<biblScope unit="issue">1</biblScope>
<biblScope unit="pp">29--50</biblScope>
<date type="datePub">2013</date>
</imprint>
</monogr>
<idno type="doi">10.1016/j.comgeo.2012.03.003</idno>
</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="ART">Journal articles</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, $O(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/Corpus

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

HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 003690 | SxmlIndent | more

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

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Hal
   |étape=   Corpus
   |type=    RBID
   |clé=     Hal:hal-00684510
   |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 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