Monotone drawings of 3-Connected plane graphs

Xin He; Dayu He

doi:10.1007/978-3-662-48350-3_61

Monotone drawings of 3-Connected plane graphs

Xin He
, Dayu He

Department of Computer Science and Engineering

SUNY Buffalo

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

9 Scopus citations

Abstract

A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path P_uw in G that is monotone on some line l_uw. (Namely, the order of the orthogonal projections of the vertices in P_uw on l_uw is the same as the order they appear in P_uw.) In this paper, we show that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a grid of size f × f (f ≤ 2n−5 is the number of internal faces of G), which can be constructed in O(n) time. It also has the advantage that, for any given vertices u,w, the monotone line l_uw can be identified in O(1) time.

Original language	English
Title of host publication	Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings
Editors	Nikhil Bansal, Irene Finocchi
Publisher	Springer Verlag
Pages	729-741
Number of pages	13
ISBN (Print)	9783662483497
DOIs	https://doi.org/10.1007/978-3-662-48350-3_61
State	Published - 2015
Event	23rd European Symposium on Algorithms, ESA 2015 - Patras, Greece Duration: Sep 14 2015 → Sep 16 2015

Publication series

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

Conference

Conference	23rd European Symposium on Algorithms, ESA 2015
Country/Territory	Greece
City	Patras
Period	09/14/15 → 09/16/15

Access to Document

10.1007/978-3-662-48350-3_61

Cite this

He, X., & He, D. (2015). Monotone drawings of 3-Connected plane graphs. In N. Bansal, & I. Finocchi (Eds.), Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings (pp. 729-741). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294). Springer Verlag. https://doi.org/10.1007/978-3-662-48350-3_61

@inproceedings{45511b438a6148608ebfaeeb2f04cab7,

title = "Monotone drawings of 3-Connected plane graphs",

abstract = "A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path Puw in G that is monotone on some line luw. (Namely, the order of the orthogonal projections of the vertices in Puw on luw is the same as the order they appear in Puw.) In this paper, we show that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a grid of size f × f (f ≤ 2n−5 is the number of internal faces of G), which can be constructed in O(n) time. It also has the advantage that, for any given vertices u,w, the monotone line luw can be identified in O(1) time.",

author = "Xin He and Dayu He",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 23rd European Symposium on Algorithms, ESA 2015 ; Conference date: 14-09-2015 Through 16-09-2015",

year = "2015",

doi = "10.1007/978-3-662-48350-3\_61",

language = "English",

isbn = "9783662483497",

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

publisher = "Springer Verlag",

pages = "729--741",

editor = "Nikhil Bansal and Irene Finocchi",

booktitle = "Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings",

address = "Germany",

}

He, X & He, D 2015, Monotone drawings of 3-Connected plane graphs. in N Bansal & I Finocchi (eds), Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9294, Springer Verlag, pp. 729-741, 23rd European Symposium on Algorithms, ESA 2015, Patras, Greece, 09/14/15. https://doi.org/10.1007/978-3-662-48350-3_61

Monotone drawings of 3-Connected plane graphs. / He, Xin; He, Dayu.
Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings. ed. / Nikhil Bansal; Irene Finocchi. Springer Verlag, 2015. p. 729-741 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294).

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

TY - GEN

T1 - Monotone drawings of 3-Connected plane graphs

AU - He, Xin

AU - He, Dayu

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path Puw in G that is monotone on some line luw. (Namely, the order of the orthogonal projections of the vertices in Puw on luw is the same as the order they appear in Puw.) In this paper, we show that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a grid of size f × f (f ≤ 2n−5 is the number of internal faces of G), which can be constructed in O(n) time. It also has the advantage that, for any given vertices u,w, the monotone line luw can be identified in O(1) time.

AB - A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path Puw in G that is monotone on some line luw. (Namely, the order of the orthogonal projections of the vertices in Puw on luw is the same as the order they appear in Puw.) In this paper, we show that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a grid of size f × f (f ≤ 2n−5 is the number of internal faces of G), which can be constructed in O(n) time. It also has the advantage that, for any given vertices u,w, the monotone line luw can be identified in O(1) time.

UR - https://www.scopus.com/pages/publications/84945574279

U2 - 10.1007/978-3-662-48350-3_61

DO - 10.1007/978-3-662-48350-3_61

M3 - Conference contribution

AN - SCOPUS:84945574279

SN - 9783662483497

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

SP - 729

EP - 741

BT - Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings

A2 - Bansal, Nikhil

A2 - Finocchi, Irene

PB - Springer Verlag

T2 - 23rd European Symposium on Algorithms, ESA 2015

Y2 - 14 September 2015 through 16 September 2015

ER -

Monotone drawings of 3-Connected plane graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this