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 Nba684014f500412ebc8b5349d44f22e7
    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 N74ee24e0d273493ea894622efb01a8ad
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N8f4443859d3043c98876b0d385e7e88a
    14 schema:name Planar drawings and angular resolution: Algorithms and bounds
    15 schema:pagination 12-23
    16 schema:productId N2bb31d0bd8a440e38d24a28c46735c6c
    17 N35a9e878ed75464388cf5de3db26dc6e
    18 Nc02dd0f2e7774cc0af430d5d2d55a5c0
    19 schema:publisher N50299a1b3b64406ca1af51faa9148d5c
    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 N44d8bff2dd7148b7835511ee3b29a7fa
    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 N2bb31d0bd8a440e38d24a28c46735c6c schema:name dimensions_id
    30 schema:value pub.1031647520
    31 rdf:type schema:PropertyValue
    32 N35a9e878ed75464388cf5de3db26dc6e schema:name readcube_id
    33 schema:value 96c3609ba1d562f9122fbc4552070c6da02d3fdad4a7940dec1717d6eb3b5bd7
    34 rdf:type schema:PropertyValue
    35 N44d8bff2dd7148b7835511ee3b29a7fa schema:name Springer Nature - SN SciGraph project
    36 rdf:type schema:Organization
    37 N50299a1b3b64406ca1af51faa9148d5c schema:location Berlin, Heidelberg
    38 schema:name Springer Berlin Heidelberg
    39 rdf:type schema:Organisation
    40 N74ee24e0d273493ea894622efb01a8ad rdf:first Nf2a8ba30b5d24baaa5b871f90f088fb5
    41 rdf:rest rdf:nil
    42 N8f4443859d3043c98876b0d385e7e88a schema:isbn 978-3-540-48794-4
    43 978-3-540-58434-6
    44 schema:name Algorithms — ESA '94
    45 rdf:type schema:Book
    46 Nb34cbe7652144fe6a96866b6b8118c2e rdf:first sg:person.0674326220.33
    47 rdf:rest rdf:nil
    48 Nba684014f500412ebc8b5349d44f22e7 rdf:first sg:person.013377047435.30
    49 rdf:rest Nb34cbe7652144fe6a96866b6b8118c2e
    50 Nc02dd0f2e7774cc0af430d5d2d55a5c0 schema:name doi
    51 schema:value 10.1007/bfb0049393
    52 rdf:type schema:PropertyValue
    53 Nf2a8ba30b5d24baaa5b871f90f088fb5 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)


    ...