Compact monotone drawing of trees

Xin He; Dayu He

doi:10.1007/978-3-319-21398-9_36

Compact monotone drawing of trees

Xin He
, Dayu He

Department of Computer Science and Engineering

SUNY Buffalo

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

5 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_uwin G that is monotone in some direction l. (Namely, the order of the orthogonal projections of the vertices of P_uwon l is the same as the order they appear in P_uw.) The problem of finding monotone drawing for trees has been studied in several recent papers. The main focus is to reduce the size of the drawing. Currently, the smallest drawing size is O(n^1.5) × O(n^1.5). In this paper, we present a linear time algorithm for constructing monotone drawing of trees on a grid of size at most O(n^1.205) × O(n^1.205). This is the first result achieving o(n³) drawing area for solving this problem.

Original language	English
Title of host publication	Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings
Editors	Dachuan Xu, Donglei Du, Dingzhu Du
Publisher	Springer Verlag
Pages	457-468
Number of pages	12
ISBN (Print)	9783319213972
DOIs	https://doi.org/10.1007/978-3-319-21398-9_36
State	Published - 2015
Event	21st International Conference on Computing and Combinatorics Conference, COCOON 2015 - Beijing, China Duration: Aug 4 2015 → Aug 6 2015

Publication series

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

Conference

Conference	21st International Conference on Computing and Combinatorics Conference, COCOON 2015
Country/Territory	China
City	Beijing
Period	08/4/15 → 08/6/15

Access to Document

10.1007/978-3-319-21398-9_36

Cite this

He, X., & He, D. (2015). Compact monotone drawing of trees. In D. Xu, D. Du, & D. Du (Eds.), Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings (pp. 457-468). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9198). Springer Verlag. https://doi.org/10.1007/978-3-319-21398-9_36

@inproceedings{5b1d74f1a5eb4393a4cf7737a002ea2a,

title = "Compact monotone drawing of trees",

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 Puwin G that is monotone in some direction l. (Namely, the order of the orthogonal projections of the vertices of Puwon l is the same as the order they appear in Puw.) The problem of finding monotone drawing for trees has been studied in several recent papers. The main focus is to reduce the size of the drawing. Currently, the smallest drawing size is O(n1.5) × O(n1.5). In this paper, we present a linear time algorithm for constructing monotone drawing of trees on a grid of size at most O(n1.205) × O(n1.205). This is the first result achieving o(n3) drawing area for solving this problem.",

author = "Xin He and Dayu He",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 21st International Conference on Computing and Combinatorics Conference, COCOON 2015 ; Conference date: 04-08-2015 Through 06-08-2015",

year = "2015",

doi = "10.1007/978-3-319-21398-9\_36",

language = "English",

isbn = "9783319213972",

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

publisher = "Springer Verlag",

pages = "457--468",

editor = "Dachuan Xu and Donglei Du and Dingzhu Du",

booktitle = "Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings",

address = "Germany",

}

He, X & He, D 2015, Compact monotone drawing of trees. in D Xu, D Du & D Du (eds), Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9198, Springer Verlag, pp. 457-468, 21st International Conference on Computing and Combinatorics Conference, COCOON 2015, Beijing, China, 08/4/15. https://doi.org/10.1007/978-3-319-21398-9_36

Compact monotone drawing of trees. / He, Xin; He, Dayu.
Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings. ed. / Dachuan Xu; Donglei Du; Dingzhu Du. Springer Verlag, 2015. p. 457-468 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9198).

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

TY - GEN

T1 - Compact monotone drawing of trees

AU - He, Xin

AU - He, Dayu

N1 - Publisher Copyright: © Springer International Publishing Switzerland 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 Puwin G that is monotone in some direction l. (Namely, the order of the orthogonal projections of the vertices of Puwon l is the same as the order they appear in Puw.) The problem of finding monotone drawing for trees has been studied in several recent papers. The main focus is to reduce the size of the drawing. Currently, the smallest drawing size is O(n1.5) × O(n1.5). In this paper, we present a linear time algorithm for constructing monotone drawing of trees on a grid of size at most O(n1.205) × O(n1.205). This is the first result achieving o(n3) drawing area for solving this problem.

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 Puwin G that is monotone in some direction l. (Namely, the order of the orthogonal projections of the vertices of Puwon l is the same as the order they appear in Puw.) The problem of finding monotone drawing for trees has been studied in several recent papers. The main focus is to reduce the size of the drawing. Currently, the smallest drawing size is O(n1.5) × O(n1.5). In this paper, we present a linear time algorithm for constructing monotone drawing of trees on a grid of size at most O(n1.205) × O(n1.205). This is the first result achieving o(n3) drawing area for solving this problem.

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

U2 - 10.1007/978-3-319-21398-9_36

DO - 10.1007/978-3-319-21398-9_36

M3 - Conference contribution

AN - SCOPUS:84951151055

SN - 9783319213972

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

SP - 457

EP - 468

BT - Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings

A2 - Xu, Dachuan

A2 - Du, Donglei

A2 - Du, Dingzhu

PB - Springer Verlag

T2 - 21st International Conference on Computing and Combinatorics Conference, COCOON 2015

Y2 - 4 August 2015 through 6 August 2015

ER -

Compact monotone drawing of trees

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this