Periodic planar straight-frame drawings with polynomial resolution

Luca Castelli Aleardi; Éric Fusy; Anatolii Kostrygin

doi:10.1007/978-3-642-54423-1_15

Periodic planar straight-frame drawings with polynomial resolution

Luca Castelli Aleardi
, Éric Fusy
, Anatolii Kostrygin

Laboratoire d'Informatique (LIX)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We present a new algorithm to compute periodic (planar) straight-line drawings of toroidal graphs. Our algorithm is the first to achieve two important aesthetic criteria: the drawing fits in a straight rectangular frame, and the grid area is polynomial, precisely the grid size is O(n ⁴×n ⁴). This solves one of the main open problems in a recent paper by Duncan et al. [3].

Original language	English
Title of host publication	LATIN 2014
Subtitle of host publication	Theoretical Informatics - 11th Latin American Symposium, Proceedings
Publisher	Springer Verlag
Pages	168-179
Number of pages	12
ISBN (Print)	9783642544224
DOIs	https://doi.org/10.1007/978-3-642-54423-1_15
Publication status	Published - 1 Jan 2014
Event	11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay Duration: 31 Mar 2014 → 4 Apr 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8392 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th Latin American Theoretical Informatics Symposium, LATIN 2014
Country/Territory	Uruguay
City	Montevideo
Period	31/03/14 → 4/04/14

Access to Document

10.1007/978-3-642-54423-1_15

Cite this

Castelli Aleardi, L., Fusy, É., & Kostrygin, A. (2014). Periodic planar straight-frame drawings with polynomial resolution. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings (pp. 168-179). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-54423-1_15

Castelli Aleardi, Luca ; Fusy, Éric ; Kostrygin, Anatolii. / Periodic planar straight-frame drawings with polynomial resolution. LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag, 2014. pp. 168-179 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{abfc29a2452643199fdaed6e1e4219dd,

title = "Periodic planar straight-frame drawings with polynomial resolution",

abstract = "We present a new algorithm to compute periodic (planar) straight-line drawings of toroidal graphs. Our algorithm is the first to achieve two important aesthetic criteria: the drawing fits in a straight rectangular frame, and the grid area is polynomial, precisely the grid size is O(n 4×n 4). This solves one of the main open problems in a recent paper by Duncan et al. [3].",

author = "\{Castelli Aleardi\}, Luca and {\'E}ric Fusy and Anatolii Kostrygin",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-642-54423-1\_15",

language = "English",

isbn = "9783642544224",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "168--179",

booktitle = "LATIN 2014",

note = "11th Latin American Theoretical Informatics Symposium, LATIN 2014 ; Conference date: 31-03-2014 Through 04-04-2014",

}

Castelli Aleardi, L, Fusy, É & Kostrygin, A 2014, Periodic planar straight-frame drawings with polynomial resolution. in LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8392 LNCS, Springer Verlag, pp. 168-179, 11th Latin American Theoretical Informatics Symposium, LATIN 2014, Montevideo, Uruguay, 31/03/14. https://doi.org/10.1007/978-3-642-54423-1_15

Periodic planar straight-frame drawings with polynomial resolution. / Castelli Aleardi, Luca; Fusy, Éric; Kostrygin, Anatolii.
LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag, 2014. p. 168-179 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Periodic planar straight-frame drawings with polynomial resolution

AU - Castelli Aleardi, Luca

AU - Fusy, Éric

AU - Kostrygin, Anatolii

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We present a new algorithm to compute periodic (planar) straight-line drawings of toroidal graphs. Our algorithm is the first to achieve two important aesthetic criteria: the drawing fits in a straight rectangular frame, and the grid area is polynomial, precisely the grid size is O(n 4×n 4). This solves one of the main open problems in a recent paper by Duncan et al. [3].

AB - We present a new algorithm to compute periodic (planar) straight-line drawings of toroidal graphs. Our algorithm is the first to achieve two important aesthetic criteria: the drawing fits in a straight rectangular frame, and the grid area is polynomial, precisely the grid size is O(n 4×n 4). This solves one of the main open problems in a recent paper by Duncan et al. [3].

U2 - 10.1007/978-3-642-54423-1_15

DO - 10.1007/978-3-642-54423-1_15

M3 - Conference contribution

AN - SCOPUS:84899986845

SN - 9783642544224

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 168

EP - 179

BT - LATIN 2014

PB - Springer Verlag

T2 - 11th Latin American Theoretical Informatics Symposium, LATIN 2014

Y2 - 31 March 2014 through 4 April 2014

ER -

Castelli Aleardi L, Fusy É, Kostrygin A. Periodic planar straight-frame drawings with polynomial resolution. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag. 2014. p. 168-179. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-54423-1_15

Periodic planar straight-frame drawings with polynomial resolution

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this