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 Naf0447406555444690c868eea77c80a3
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 Nb17d5382aebf40de9687eb6b57c8d451
17 Ne8ca4e9a5efd4187b5057eba8571e52b
18 sg:journal.1133515
19 schema:name The complexity of drawing trees nicely
20 schema:pagination 377-392
21 schema:productId N3df35663b8594037bc5777dafdfd88ec
22 N6eb80b21fc5746a590372093dd243180
23 N7aebd39629354ef09d03ec6747b45f89
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 N7e5e3b6434d6461189213d4ec2b1b327
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 N14d3144976594803ba39a172845a4f33 rdf:first sg:person.01215667224.77
34 rdf:rest rdf:nil
35 N3df35663b8594037bc5777dafdfd88ec schema:name dimensions_id
36 schema:value pub.1004282920
37 rdf:type schema:PropertyValue
38 N6eb80b21fc5746a590372093dd243180 schema:name readcube_id
39 schema:value 1468857218a6204dd5f42209ca215f9bbfbad5c8ea61aa0c27e9258a939d96bf
40 rdf:type schema:PropertyValue
41 N7aebd39629354ef09d03ec6747b45f89 schema:name doi
42 schema:value 10.1007/bf00289576
43 rdf:type schema:PropertyValue
44 N7e5e3b6434d6461189213d4ec2b1b327 schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 Naf0447406555444690c868eea77c80a3 rdf:first sg:person.013052610621.81
47 rdf:rest N14d3144976594803ba39a172845a4f33
48 Nb17d5382aebf40de9687eb6b57c8d451 schema:issueNumber 4
49 rdf:type schema:PublicationIssue
50 Ne8ca4e9a5efd4187b5057eba8571e52b schema:volumeNumber 18
51 rdf:type schema:PublicationVolume
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)


...