Planar drawings and angular resolution: Algorithms and bounds View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1994

AUTHORS

Ashim Garg , Roberto Tamassia

ABSTRACT

We investigate the problem of constructing planar straightline drawings of graphs with large angles between the edges. Namely, we study the angular resolution of planar straight-line drawings, defined as the smallest angle formed by two incident edges. We prove the first nontrivial upper bound on the angular resolution of planar straight-line drawings, and show a continuous trade-off between the area and the angular resolution. We also give linear-time algorithms for constructing planar straight-line drawings with high angular resolution for various classes of graphs, such as series-parallel graphs, outerplanar graphs, and triangulations generated by nested triangles. Our results are obtained by new techniques that make extensive use of geometric constructions. More... »

PAGES

12-23

References to SciGraph publications

  • 1992-04. Area requirement and symmetry display of planar upward drawings in DISCRETE & COMPUTATIONAL GEOMETRY
  • Book

    TITLE

    Algorithms — ESA '94

    ISBN

    978-3-540-58434-6
    978-3-540-48794-4

    Author Affiliations

    From Grant

    Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Brown University", 
              "id": "https://www.grid.ac/institutes/grid.40263.33", 
              "name": [
                "Department of Computer Science, Brown University, 02912-1910\u00a0Providence, RI, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Garg", 
            "givenName": "Ashim", 
            "id": "sg:person.013377047435.30", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013377047435.30"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Brown University", 
              "id": "https://www.grid.ac/institutes/grid.40263.33", 
              "name": [
                "Department of Computer Science, Brown University, 02912-1910\u00a0Providence, RI, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tamassia", 
            "givenName": "Roberto", 
            "id": "sg:person.0674326220.33", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0020-0190(80)90034-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049102337"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187850", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053554536", 
              "https://doi.org/10.1007/bf02187850"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187850", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053554536", 
              "https://doi.org/10.1007/bf02187850"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1994", 
        "datePublishedReg": "1994-01-01", 
        "description": "We investigate the problem of constructing planar straightline drawings of graphs with large angles between the edges. Namely, we study the angular resolution of planar straight-line drawings, defined as the smallest angle formed by two incident edges. We prove the first nontrivial upper bound on the angular resolution of planar straight-line drawings, and show a continuous trade-off between the area and the angular resolution. We also give linear-time algorithms for constructing planar straight-line drawings with high angular resolution for various classes of graphs, such as series-parallel graphs, outerplanar graphs, and triangulations generated by nested triangles. Our results are obtained by new techniques that make extensive use of geometric constructions.", 
        "editor": [
          {
            "familyName": "van Leeuwen", 
            "givenName": "Jan", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/bfb0049393", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3382805", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-3-540-58434-6", 
            "978-3-540-48794-4"
          ], 
          "name": "Algorithms \u2014 ESA '94", 
          "type": "Book"
        }, 
        "name": "Planar drawings and angular resolution: Algorithms and bounds", 
        "pagination": "12-23", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bfb0049393"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "96c3609ba1d562f9122fbc4552070c6da02d3fdad4a7940dec1717d6eb3b5bd7"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1031647520"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/bfb0049393", 
          "https://app.dimensions.ai/details/publication/pub.1031647520"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T13:28", 
        "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/0000000001_0000000264/records_8664_00000262.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/BFb0049393"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    81 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bfb0049393 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nb8f951bc0d9c496ebb932059c2bb28a7
    4 schema:citation sg:pub.10.1007/bf02187850
    5 https://doi.org/10.1016/0020-0190(80)90034-4
    6 schema:datePublished 1994
    7 schema:datePublishedReg 1994-01-01
    8 schema:description We investigate the problem of constructing planar straightline drawings of graphs with large angles between the edges. Namely, we study the angular resolution of planar straight-line drawings, defined as the smallest angle formed by two incident edges. We prove the first nontrivial upper bound on the angular resolution of planar straight-line drawings, and show a continuous trade-off between the area and the angular resolution. We also give linear-time algorithms for constructing planar straight-line drawings with high angular resolution for various classes of graphs, such as series-parallel graphs, outerplanar graphs, and triangulations generated by nested triangles. Our results are obtained by new techniques that make extensive use of geometric constructions.
    9 schema:editor N7f82a09966c543ce923be1fb552f8e98
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N69a7806840474e50971c5f037c977972
    14 schema:name Planar drawings and angular resolution: Algorithms and bounds
    15 schema:pagination 12-23
    16 schema:productId N7518daa824c74958b4ed0a029a34b00c
    17 Na33f917f95354d0fbb0806bbe1b753a6
    18 Nb7f2202884c94292bdd56d154da2ee86
    19 schema:publisher Ne8621971eb9942aba2694f7fc122e26c
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031647520
    21 https://doi.org/10.1007/bfb0049393
    22 schema:sdDatePublished 2019-04-15T13:28
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher N6579736ea6eb42cdab429d93a7524af9
    25 schema:url http://link.springer.com/10.1007/BFb0049393
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset chapters
    28 rdf:type schema:Chapter
    29 N3dd99535b4414887893ece051ffdb5bc schema:familyName van Leeuwen
    30 schema:givenName Jan
    31 rdf:type schema:Person
    32 N6579736ea6eb42cdab429d93a7524af9 schema:name Springer Nature - SN SciGraph project
    33 rdf:type schema:Organization
    34 N69a7806840474e50971c5f037c977972 schema:isbn 978-3-540-48794-4
    35 978-3-540-58434-6
    36 schema:name Algorithms — ESA '94
    37 rdf:type schema:Book
    38 N7518daa824c74958b4ed0a029a34b00c schema:name doi
    39 schema:value 10.1007/bfb0049393
    40 rdf:type schema:PropertyValue
    41 N7f82a09966c543ce923be1fb552f8e98 rdf:first N3dd99535b4414887893ece051ffdb5bc
    42 rdf:rest rdf:nil
    43 Na33f917f95354d0fbb0806bbe1b753a6 schema:name dimensions_id
    44 schema:value pub.1031647520
    45 rdf:type schema:PropertyValue
    46 Nb7f2202884c94292bdd56d154da2ee86 schema:name readcube_id
    47 schema:value 96c3609ba1d562f9122fbc4552070c6da02d3fdad4a7940dec1717d6eb3b5bd7
    48 rdf:type schema:PropertyValue
    49 Nb8f951bc0d9c496ebb932059c2bb28a7 rdf:first sg:person.013377047435.30
    50 rdf:rest Ne1d83deae08240a9803df741850969e6
    51 Ne1d83deae08240a9803df741850969e6 rdf:first sg:person.0674326220.33
    52 rdf:rest rdf:nil
    53 Ne8621971eb9942aba2694f7fc122e26c schema:location Berlin, Heidelberg
    54 schema:name Springer Berlin Heidelberg
    55 rdf:type schema:Organisation
    56 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Mathematical Sciences
    58 rdf:type schema:DefinedTerm
    59 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Pure Mathematics
    61 rdf:type schema:DefinedTerm
    62 sg:grant.3382805 http://pending.schema.org/fundedItem sg:pub.10.1007/bfb0049393
    63 rdf:type schema:MonetaryGrant
    64 sg:person.013377047435.30 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
    65 schema:familyName Garg
    66 schema:givenName Ashim
    67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013377047435.30
    68 rdf:type schema:Person
    69 sg:person.0674326220.33 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
    70 schema:familyName Tamassia
    71 schema:givenName Roberto
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33
    73 rdf:type schema:Person
    74 sg:pub.10.1007/bf02187850 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053554536
    75 https://doi.org/10.1007/bf02187850
    76 rdf:type schema:CreativeWork
    77 https://doi.org/10.1016/0020-0190(80)90034-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049102337
    78 rdf:type schema:CreativeWork
    79 https://www.grid.ac/institutes/grid.40263.33 schema:alternateName Brown University
    80 schema:name Department of Computer Science, Brown University, 02912-1910 Providence, RI, USA
    81 rdf:type schema:Organization
     




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


    ...