On Point-sets that Support Planar Graphs

Vida Dujmovic; Will Evans; Sylvain Lazard; William Lenhart; Giuseppe Liotta; David Rappaport; Steve Wismath

hal-00684510, version 1

On Point-sets that Support Planar Graphs

Vida Dujmovic^a^, 1, Will Evans ², Sylvain Lazard (, ) ³, William Lenhart^b^, 4, Giuseppe Liotta^c^, 5, David Rappaport ⁶, Steve Wismath^d^, 7

Computational Geometry 43, 1 (2013) 29--50

Résumé : 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.

a – Carleton University
b – Williams College
c – Universita degli Studi di Perugua
d – UNIVERSITY OF LETHBRIDGE
1 : School of computer science [Ottawa] (SCS)
Carleton University
2 : Computer Science Department (UBC-Computer Science)
University of British Columbia
3 : VEGAS (INRIA Nancy - Grand Est / LORIA)
INRIA – CNRS : UMR7503 – Université de Lorraine
4 : Computer Science Department [Williamstown MA]
Williams College
5 : School of Computing
University of Perugia
6 : Department of Electrical and Computer Engineering [Queen's University Kingston]
Queen's University
7 : Department of Mathematics and Computer Science
University of Lethbridge

hal-00684510, version 1
http://hal.inria.fr/hal-00684510
oai:hal.inria.fr:hal-00684510
Contributeur : Sylvain Lazard <>
Soumis le : Lundi 2 Avril 2012, 12:17:43
Dernière modification le : Vendredi 26 Octobre 2012, 15:20:09

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1016/j.comgeo.2012.03.003

Exporter

Bibtex EndNote TEI RefWorks

%% hal-00684510, version 1
%% http://hal.inria.fr/hal-00684510
@article{dujmovic:hal-00684510,
    hal_id = {hal-00684510},
    url = {http://hal.inria.fr/hal-00684510},
    title = {{On Point-sets that Support Planar Graphs}},
    author = {Dujmovic, Vida and Evans, Will and Lazard, Sylvain and Lenhart, William and Liotta, Giuseppe and Rappaport, David and Wismath, Steve},
    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.}},
    language = {Anglais},
    affiliation = {School of computer science [Ottawa] - SCS , Computer Science Department - UBC-Computer Science , VEGAS - INRIA Nancy - Grand Est / LORIA , Computer Science Department [Williamstown MA] , School of Computing , Department of Electrical and Computer Engineering [Queen's University Kingston] , Department of Mathematics and Computer Science},
    publisher = {Elsevier},
    pages = {29--50},
    journal = {Computational Geometry},
    volume = {43},
    number = {1 },
    audience = {internationale },
    doi = {10.1016/j.comgeo.2012.03.003 },
    year = {2013},
    pdf = {http://hal.inria.fr/hal-00684510/PDF/journalversion.pdf},
}

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="hal-00684510"><analytic>
<author><persName><forename>Vida</forename><surname>Dujmovic</surname></persName>
<affiliation>
<orgName type="laboratory">SCS</orgName>
<orgName type="team">School of computer science [Ottawa]</orgName>
<country>CA</country>
<orgName type="institution">Carleton University</orgName>
</affiliation>
</author>
<author><persName><forename>Will</forename><surname>Evans</surname></persName>
<affiliation>
<orgName type="laboratory">UBC-Computer Science</orgName>
<orgName type="team">Computer Science Department</orgName>
<country>CA</country>
<orgName type="institution">University of British Columbia</orgName>
</affiliation>
</author>
<author><persName><forename>Sylvain</forename><surname>Lazard</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Nancy - Grand Est / LORIA</orgName>
<orgName type="team">VEGAS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>William</forename><surname>Lenhart</surname></persName>
<affiliation>
<orgName type="team">Computer Science Department [Williamstown MA]</orgName>
<country>US</country>
<orgName type="institution">Williams College</orgName>
</affiliation>
</author>
<author><persName><forename>Giuseppe</forename><surname>Liotta</surname></persName>
<affiliation>
<orgName type="team">School of Computing</orgName>
<country>IT</country>
<orgName type="institution">University of Perugia</orgName>
</affiliation>
</author>
<author><persName><forename>David</forename><surname>Rappaport</surname></persName>
<affiliation>
<orgName type="team">Department of Electrical and Computer Engineering [Queen's University Kingston]</orgName>
<country>CA</country>
<orgName type="institution">Queen's University</orgName>
</affiliation>
</author>
<author><persName><forename>Steve</forename><surname>Wismath</surname></persName>
<affiliation>
<orgName type="team">Department of Mathematics and Computer Science</orgName>
<country>CA</country>
<orgName type="institution">University of Lethbridge</orgName>
</affiliation>
</author>
<title type="main" level="a">On Point-sets that Support Planar Graphs</title></analytic><monogr><title level="j" type="main">Computational Geometry</title><imprint><publisher>Elsevier</publisher><biblScope type="publicationDate">2013-00-00</biblScope><biblScope type="vol">43</biblScope><biblScope type="issue">1</biblScope><biblScope type="pp">29--50</biblScope></imprint></monogr><idno type="doi">10.1016/j.comgeo.2012.03.003</idno><idno type="HALid">http://hal.inria.fr/hal-00684510</idno><idno type="HALFile">http://hal.inria.fr/hal-00684510/PDF/journalversion.pdf</idno></biblStruct>
</listBibl>
</listBibl>