Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices

Hazel Everett; Sylvain Lazard; Giuseppe Liotta; Steve Wismath

inria-00189036, version 1

Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices

Hazel Everett ()^a^, 1, Sylvain Lazard ()^b^, 1, Giuseppe Liotta ², Steve Wismath^c^, 3

The 15th International Symposium on Graph Drawing - GD 2007 LNCS 4875 (2007) 345-351

Résumé : This paper shows that any planar graph with n vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that any number of planar graphs admit a simultaneous embedding without mapping with at most one bend per edge.

a – Université Nancy II
b – INRIA
c – UNIVERSITY OF LETHBRIDGE
1 : VEGAS (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
2 : Dip. di Ingegneria Elettronica e dell'Informazione
Università degli studi di Perugia
3 : Department of Mathematics and Computer Science
University of Lethbridge

inria-00189036, version 1
http://hal.inria.fr/inria-00189036
oai:hal.inria.fr:inria-00189036
Contributeur : Sylvain Lazard <>
Soumis le : Lundi 19 Novembre 2007, 18:36:51
Dernière modification le : Dimanche 20 Décembre 2009, 14:50:05

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1007/978-3-540-77537-9_34

Exporter

Bibtex EndNote TEI RefWorks

<?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="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="inria-00189036"><analytic>
<author><persName><forename>Hazel</forename><surname>Everett</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - 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é Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Sylvain</forename><surname>Lazard</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - 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é Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Giuseppe</forename><surname>Liotta</surname></persName>
<affiliation>
<orgName type="team">Dip. di Ingegneria Elettronica e dell'Informazione</orgName>
<country>IT</country>
<orgName type="institution">Università degli studi di Perugia</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">Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices</title></analytic><monogr><meeting>The 15th International Symposium on Graph Drawing - GD 2007</meeting><imprint><publisher>Springer-Verlag</publisher><pubPlace><settlement>Sydney</settlement><country>Australie</country></pubPlace><biblScope type="publicationDate">2008-00-00</biblScope><biblScope type="vol">LNCS 4875</biblScope><biblScope type="pp">345-351</biblScope></imprint></monogr><idno type="doi">10.1007/978-3-540-77537-9_34</idno><idno type="HALid">http://hal.inria.fr/inria-00189036</idno><idno type="HALFile">http://hal.inria.fr/inria-00189036/PDF/GD07_FINAL.pdf</idno></biblStruct>
</listBibl>
</listBibl>