# Compact Monotone Drawing of Trees

Ontology type: schema:Chapter

### Chapter Info

DATE

2015-06-24

AUTHORS 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{uw}$$\end{document} in G that is monotone in some direction l. (Namely, the order of the orthogonal projections of the vertices of Puw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{uw}$$\end{document} on l is the same as the order they appear in Puw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{uw}$$\end{document}.)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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{1.5}) \times O(n^{1.5})$$\end{document}. 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{1.205}) \times O(n^{1.205})$$\end{document}. This is the first result achieving o(n3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$o(n^3)$$\end{document} drawing area for solving this problem. More... »

PAGES

457-468

### Book

TITLE

Computing and Combinatorics

ISBN

978-3-319-21397-2
978-3-319-21398-9

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_36

DOI

http://dx.doi.org/10.1007/978-3-319-21398-9_36

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1008183639

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Language, Communication and Culture",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2002",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Cultural Studies",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA",
"id": "http://www.grid.ac/institutes/grid.273335.3",
"name": [
"Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA"
],
"type": "Organization"
},
"familyName": "He",
"givenName": "Xin",
"id": "sg:person.011352641523.42",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA",
"id": "http://www.grid.ac/institutes/grid.273335.3",
"name": [
"Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA"
],
"type": "Organization"
},
"familyName": "He",
"givenName": "Dayu",
"id": "sg:person.011772764733.17",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011772764733.17"
],
"type": "Person"
}
],
"datePublished": "2015-06-24",
"datePublishedReg": "2015-06-24",
"description": "A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,\u00a0w in G, there exists a path Puw\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$P_{uw}$$\\end{document} in G that is monotone in some direction l. (Namely, the order of the orthogonal projections of the vertices of Puw\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$P_{uw}$$\\end{document} on l is the same as the order they appear in Puw\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$P_{uw}$$\\end{document}.)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)\u00d7O(n1.5)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(n^{1.5}) \\times O(n^{1.5})$$\\end{document}. 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)\u00d7O(n1.205)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(n^{1.205}) \\times O(n^{1.205})$$\\end{document}. This is the first result achieving o(n3)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$o(n^3)$$\\end{document} drawing area for solving this problem.",
"editor": [
{
"familyName": "Xu",
"givenName": "Dachuan",
"type": "Person"
},
{
"familyName": "Du",
"givenName": "Donglei",
"type": "Person"
},
{
"familyName": "Du",
"givenName": "Dingzhu",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-21398-9_36",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-319-21397-2",
"978-3-319-21398-9"
],
"name": "Computing and Combinatorics",
"type": "Book"
},
"keywords": [
"size",
"projections",
"focus",
"results",
"area",
"drawing area",
"L.",
"order",
"orthogonal projection",
"problem",
"main focus",
"drawings",
"pairs",
"recent paper",
"first results",
"trees",
"paper",
"vertices u",
"path",
"vertices",
"graph G",
"algorithm",
"monotone",
"linear time algorithm",
"time algorithm",
"grid",
"straight-line drawing",
"monotone drawing",
"direction l.",
"smallest drawing size",
"drawing size",
"grid of size",
"Compact Monotone Drawing"
],
"name": "Compact Monotone Drawing of Trees",
"pagination": "457-468",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1008183639"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-21398-9_36"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-21398-9_36",
"https://app.dimensions.ai/details/publication/pub.1008183639"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-11-01T18:47",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_144.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-319-21398-9_36"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_36'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_36'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_36'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21398-9_36'

This table displays all metadata directly associated to this object as RDF triples.

110 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:2002
3 schema:author Nde83ca16e0ab4a89a0f194fd74266b66
4 schema:datePublished 2015-06-24
5 schema:datePublishedReg 2015-06-24
6 schema:description 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{uw}$$\end{document} in G that is monotone in some direction l. (Namely, the order of the orthogonal projections of the vertices of Puw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{uw}$$\end{document} on l is the same as the order they appear in Puw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{uw}$$\end{document}.)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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{1.5}) \times O(n^{1.5})$$\end{document}. 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^{1.205}) \times O(n^{1.205})$$\end{document}. This is the first result achieving o(n3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$o(n^3)$$\end{document} drawing area for solving this problem.
7 schema:editor N482bf1a73833450e99dd49be56c703f5
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N03598bdcc70e4290aaa195a820b34a76
12 schema:keywords Compact Monotone Drawing
13 L.
14 algorithm
15 area
16 direction l.
17 drawing area
18 drawing size
19 drawings
20 first results
21 focus
22 graph G
23 grid
24 grid of size
25 linear time algorithm
26 main focus
27 monotone
28 monotone drawing
29 order
30 orthogonal projection
31 pairs
32 paper
33 path
34 problem
35 projections
36 recent paper
37 results
38 size
39 smallest drawing size
40 straight-line drawing
41 time algorithm
42 trees
43 vertices
44 vertices u
45 schema:name Compact Monotone Drawing of Trees
46 schema:pagination 457-468
47 schema:productId N81f240fbbec54bf9abe0e6f66581cac8
48 Nca5fdf78bed6438db63b2394670dd9e9
49 schema:publisher Nb530002137ec4f728773321018cf1bc0
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008183639
51 https://doi.org/10.1007/978-3-319-21398-9_36
52 schema:sdDatePublished 2021-11-01T18:47
54 schema:sdPublisher N8a4bbb7e38904062864307192ec5d6cb
55 schema:url https://doi.org/10.1007/978-3-319-21398-9_36
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N03598bdcc70e4290aaa195a820b34a76 schema:isbn 978-3-319-21397-2
60 978-3-319-21398-9
61 schema:name Computing and Combinatorics
62 rdf:type schema:Book
63 N482bf1a73833450e99dd49be56c703f5 rdf:first Ndecd7a77855545e686d371decfcc0a3e
64 rdf:rest N8a21af98040d47f0bf2747a3f8d0ed69
65 N5bef619f879b4db787dcaf706485657e schema:familyName Du
66 schema:givenName Donglei
67 rdf:type schema:Person
68 N7ed0189f88ff43258a848cb2aafb7a2d rdf:first sg:person.011772764733.17
69 rdf:rest rdf:nil
70 N81f240fbbec54bf9abe0e6f66581cac8 schema:name doi
71 schema:value 10.1007/978-3-319-21398-9_36
72 rdf:type schema:PropertyValue
73 N8a21af98040d47f0bf2747a3f8d0ed69 rdf:first N5bef619f879b4db787dcaf706485657e
75 N8a4bbb7e38904062864307192ec5d6cb schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 Nab368f65444b42bc9b4b6e731c8452e5 schema:familyName Du
78 schema:givenName Dingzhu
79 rdf:type schema:Person
81 rdf:rest rdf:nil
82 Nb530002137ec4f728773321018cf1bc0 schema:name Springer Nature
83 rdf:type schema:Organisation
84 Nca5fdf78bed6438db63b2394670dd9e9 schema:name dimensions_id
85 schema:value pub.1008183639
86 rdf:type schema:PropertyValue
87 Nde83ca16e0ab4a89a0f194fd74266b66 rdf:first sg:person.011352641523.42
88 rdf:rest N7ed0189f88ff43258a848cb2aafb7a2d
89 Ndecd7a77855545e686d371decfcc0a3e schema:familyName Xu
90 schema:givenName Dachuan
91 rdf:type schema:Person
92 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
93 schema:name Language, Communication and Culture
94 rdf:type schema:DefinedTerm
95 anzsrc-for:2002 schema:inDefinedTermSet anzsrc-for:
96 schema:name Cultural Studies
97 rdf:type schema:DefinedTerm
98 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
99 schema:familyName He
100 schema:givenName Xin
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
102 rdf:type schema:Person
103 sg:person.011772764733.17 schema:affiliation grid-institutes:grid.273335.3
104 schema:familyName He
105 schema:givenName Dayu
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011772764733.17
107 rdf:type schema:Person
108 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
109 schema:name Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
110 rdf:type schema:Organization