The complexity of drawing trees nicely View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1983-01

AUTHORS

Kenneth J. Supowit, Edward M. Reingold

ABSTRACT

We investigate the complexity of producing aesthetically pleasing drawings of binary trees, drawings that are as narrow as possible. The notion of what is aesthetically pleasing is embodied in several constraints on the placement of nodes, relative to other nodes. Among the results we give are: (1) There is no obvious “principle of optimality” that can be applied, since globally narrow, aesthetic placements of trees may require wider than necessary subtrees. (2) A previously suggested heuristic can produce drawings on n-node trees that are Θ(n) times as wide as necessary. (3) The problem can be reduced in polynomial time to linear programming; hence, if the coordinates assigned to the nodes are continuous variables, then the problem can be solved in polynomial time. (4) If the placement is restricted to the integral lattice then the problem is NP-hard, as is its approximation to within a factor of about 4 per cent. More... »

PAGES

377-392

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf00289576

DOI

http://dx.doi.org/10.1007/bf00289576

DIMENSIONS

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


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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Illinois at Urbana Champaign", 
          "id": "https://www.grid.ac/institutes/grid.35403.31", 
          "name": [
            "Department of Computer Science, University of Illinois at Urbana-Champaign, 61801, Urbana, Illinois, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Supowit", 
        "givenName": "Kenneth J.", 
        "id": "sg:person.013052610621.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013052610621.81"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Illinois at Urbana Champaign", 
          "id": "https://www.grid.ac/institutes/grid.35403.31", 
          "name": [
            "Department of Computer Science, University of Illinois at Urbana-Champaign, 61801, Urbana, Illinois, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Reingold", 
        "givenName": "Edward M.", 
        "id": "sg:person.01215667224.77", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01215667224.77"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1090/s0002-9939-1976-0396605-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007324334"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/spe.4380100706", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018211857"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/359423.359434", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031866364"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321958.321975", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048192025"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tse.1979.234212", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061787341"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tse.1981.234519", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061787468"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1983-01", 
    "datePublishedReg": "1983-01-01", 
    "description": "We investigate the complexity of producing aesthetically pleasing drawings of binary trees, drawings that are as narrow as possible. The notion of what is aesthetically pleasing is embodied in several constraints on the placement of nodes, relative to other nodes. Among the results we give are: (1) There is no obvious \u201cprinciple of optimality\u201d that can be applied, since globally narrow, aesthetic placements of trees may require wider than necessary subtrees. (2) A previously suggested heuristic can produce drawings on n-node trees that are \u0398(n) times as wide as necessary. (3) The problem can be reduced in polynomial time to linear programming; hence, if the coordinates assigned to the nodes are continuous variables, then the problem can be solved in polynomial time. (4) If the placement is restricted to the integral lattice then the problem is NP-hard, as is its approximation to within a factor of about 4 per cent.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf00289576", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1133515", 
        "issn": [
          "0001-5903", 
          "1432-0525"
        ], 
        "name": "Acta Informatica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "18"
      }
    ], 
    "name": "The complexity of drawing trees nicely", 
    "pagination": "377-392", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00289576"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "1468857218a6204dd5f42209ca215f9bbfbad5c8ea61aa0c27e9258a939d96bf"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004282920"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00289576", 
      "https://app.dimensions.ai/details/publication/pub.1004282920"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-15T08:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000374_0000000374/records_119714_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF00289576"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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/bf00289576'

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/bf00289576'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf00289576'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf00289576'


 

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

86 TRIPLES      21 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf00289576 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N6c87cb1b736340c88c049897fe6653b4
4 schema:citation https://doi.org/10.1002/spe.4380100706
5 https://doi.org/10.1090/s0002-9939-1976-0396605-3
6 https://doi.org/10.1109/tse.1979.234212
7 https://doi.org/10.1109/tse.1981.234519
8 https://doi.org/10.1145/321958.321975
9 https://doi.org/10.1145/359423.359434
10 schema:datePublished 1983-01
11 schema:datePublishedReg 1983-01-01
12 schema:description We investigate the complexity of producing aesthetically pleasing drawings of binary trees, drawings that are as narrow as possible. The notion of what is aesthetically pleasing is embodied in several constraints on the placement of nodes, relative to other nodes. Among the results we give are: (1) There is no obvious “principle of optimality” that can be applied, since globally narrow, aesthetic placements of trees may require wider than necessary subtrees. (2) A previously suggested heuristic can produce drawings on n-node trees that are Θ(n) times as wide as necessary. (3) The problem can be reduced in polynomial time to linear programming; hence, if the coordinates assigned to the nodes are continuous variables, then the problem can be solved in polynomial time. (4) If the placement is restricted to the integral lattice then the problem is NP-hard, as is its approximation to within a factor of about 4 per cent.
13 schema:genre research_article
14 schema:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf Nc95016285fe1477cb813cadd00a85e64
17 Nf831353c564946a8a3fd127caa91bcde
18 sg:journal.1133515
19 schema:name The complexity of drawing trees nicely
20 schema:pagination 377-392
21 schema:productId N46dad87b6dee4602bb3ec23b31a71446
22 Na66d61f93af1443a89e42ddab35d9e37
23 Nde25fdb363414dc1bc3aed5e3a1c072b
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004282920
25 https://doi.org/10.1007/bf00289576
26 schema:sdDatePublished 2019-04-15T08:47
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher Ndda9a9acc72a4531a38955a520dfa25f
29 schema:url http://link.springer.com/10.1007/BF00289576
30 sgo:license sg:explorer/license/
31 sgo:sdDataset articles
32 rdf:type schema:ScholarlyArticle
33 N46dad87b6dee4602bb3ec23b31a71446 schema:name doi
34 schema:value 10.1007/bf00289576
35 rdf:type schema:PropertyValue
36 N4bbb3ca82cb145a39dc76116d9f945e3 rdf:first sg:person.01215667224.77
37 rdf:rest rdf:nil
38 N6c87cb1b736340c88c049897fe6653b4 rdf:first sg:person.013052610621.81
39 rdf:rest N4bbb3ca82cb145a39dc76116d9f945e3
40 Na66d61f93af1443a89e42ddab35d9e37 schema:name readcube_id
41 schema:value 1468857218a6204dd5f42209ca215f9bbfbad5c8ea61aa0c27e9258a939d96bf
42 rdf:type schema:PropertyValue
43 Nc95016285fe1477cb813cadd00a85e64 schema:volumeNumber 18
44 rdf:type schema:PublicationVolume
45 Ndda9a9acc72a4531a38955a520dfa25f schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 Nde25fdb363414dc1bc3aed5e3a1c072b schema:name dimensions_id
48 schema:value pub.1004282920
49 rdf:type schema:PropertyValue
50 Nf831353c564946a8a3fd127caa91bcde schema:issueNumber 4
51 rdf:type schema:PublicationIssue
52 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
53 schema:name Information and Computing Sciences
54 rdf:type schema:DefinedTerm
55 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
56 schema:name Computation Theory and Mathematics
57 rdf:type schema:DefinedTerm
58 sg:journal.1133515 schema:issn 0001-5903
59 1432-0525
60 schema:name Acta Informatica
61 rdf:type schema:Periodical
62 sg:person.01215667224.77 schema:affiliation https://www.grid.ac/institutes/grid.35403.31
63 schema:familyName Reingold
64 schema:givenName Edward M.
65 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01215667224.77
66 rdf:type schema:Person
67 sg:person.013052610621.81 schema:affiliation https://www.grid.ac/institutes/grid.35403.31
68 schema:familyName Supowit
69 schema:givenName Kenneth J.
70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013052610621.81
71 rdf:type schema:Person
72 https://doi.org/10.1002/spe.4380100706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018211857
73 rdf:type schema:CreativeWork
74 https://doi.org/10.1090/s0002-9939-1976-0396605-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007324334
75 rdf:type schema:CreativeWork
76 https://doi.org/10.1109/tse.1979.234212 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061787341
77 rdf:type schema:CreativeWork
78 https://doi.org/10.1109/tse.1981.234519 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061787468
79 rdf:type schema:CreativeWork
80 https://doi.org/10.1145/321958.321975 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048192025
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1145/359423.359434 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031866364
83 rdf:type schema:CreativeWork
84 https://www.grid.ac/institutes/grid.35403.31 schema:alternateName University of Illinois at Urbana Champaign
85 schema:name Department of Computer Science, University of Illinois at Urbana-Champaign, 61801, Urbana, Illinois, USA
86 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...