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 N15179cc406ec44d5a741d5ff4f8d40e5
    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 N7e66585a80e1492cbc90875336f28f14
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N85e046ed57ca48b4858c7f40e5531e51
    14 schema:name Planar drawings and angular resolution: Algorithms and bounds
    15 schema:pagination 12-23
    16 schema:productId N680c87e724604206a0891a836698575d
    17 N8b2377ef59fd47a38d434e2a450817dd
    18 N94bec7b953a94d2ca8a98695a1cea021
    19 schema:publisher Nb7a328ceb6e847978b9b205075acb612
    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 N31c1d25af7cf49ccb24da95f0d9189f8
    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 N09c4e933caa64ce7867c99476ace2896 rdf:first sg:person.0674326220.33
    30 rdf:rest rdf:nil
    31 N15179cc406ec44d5a741d5ff4f8d40e5 rdf:first sg:person.013377047435.30
    32 rdf:rest N09c4e933caa64ce7867c99476ace2896
    33 N31c1d25af7cf49ccb24da95f0d9189f8 schema:name Springer Nature - SN SciGraph project
    34 rdf:type schema:Organization
    35 N680c87e724604206a0891a836698575d schema:name dimensions_id
    36 schema:value pub.1031647520
    37 rdf:type schema:PropertyValue
    38 N7e66585a80e1492cbc90875336f28f14 rdf:first Nfb286c7e6bef4174a329ebffe9c05da9
    39 rdf:rest rdf:nil
    40 N85e046ed57ca48b4858c7f40e5531e51 schema:isbn 978-3-540-48794-4
    41 978-3-540-58434-6
    42 schema:name Algorithms — ESA '94
    43 rdf:type schema:Book
    44 N8b2377ef59fd47a38d434e2a450817dd schema:name doi
    45 schema:value 10.1007/bfb0049393
    46 rdf:type schema:PropertyValue
    47 N94bec7b953a94d2ca8a98695a1cea021 schema:name readcube_id
    48 schema:value 96c3609ba1d562f9122fbc4552070c6da02d3fdad4a7940dec1717d6eb3b5bd7
    49 rdf:type schema:PropertyValue
    50 Nb7a328ceb6e847978b9b205075acb612 schema:location Berlin, Heidelberg
    51 schema:name Springer Berlin Heidelberg
    52 rdf:type schema:Organisation
    53 Nfb286c7e6bef4174a329ebffe9c05da9 schema:familyName van Leeuwen
    54 schema:givenName Jan
    55 rdf:type schema:Person
    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)


    ...