A more compact visibility representation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1994

AUTHORS

Goos Kant

ABSTRACT

In this paper we present a linear time and space algorithm for constructing a visibility representation of a planar graph on an (⌊3/2n⌋−3)×(n−1) grid, thereby improving the previous bound of (2n−5)×(n−1). To this end we build in linear time the 4-block tree of a triangulated planar graph.

PAGES

411-424

References to SciGraph publications

  • 1994. Two algorithms for finding rectangular duals of planar graphs in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 1986-12. Rectilinear planar layouts and bipolar orientations of planar graphs in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1986-12. A unified approach to visibility representations of planar graphs in DISCRETE & COMPUTATIONAL GEOMETRY
  • Book

    TITLE

    Graph-Theoretic Concepts in Computer Science

    ISBN

    978-3-540-57899-4
    978-3-540-48385-4

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-57899-4_70

    DOI

    http://dx.doi.org/10.1007/3-540-57899-4_70

    DIMENSIONS

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


    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", 
        "author": [
          {
            "affiliation": {
              "alternateName": "Utrecht University", 
              "id": "https://www.grid.ac/institutes/grid.5477.1", 
              "name": [
                "Dept. of Computer Science, Utrecht University, Padualaan 14, 3584\u00a0CH Utrecht, the Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kant", 
            "givenName": "Goos", 
            "id": "sg:person.013743554756.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013743554756.94"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02187706", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008881195", 
              "https://doi.org/10.1007/bf02187706"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187706", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008881195", 
              "https://doi.org/10.1007/bf02187706"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187706", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008881195", 
              "https://doi.org/10.1007/bf02187706"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(86)90029-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012551211"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-57899-4_69", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018910920", 
              "https://doi.org/10.1007/3-540-57899-4_69"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187705", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027312329", 
              "https://doi.org/10.1007/bf02187705"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187705", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027312329", 
              "https://doi.org/10.1007/bf02187705"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/31.34669", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061153032"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0202012", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841200"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0214017", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841806"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1991.185451", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086324361"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1992.267814", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086359610"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1994", 
        "datePublishedReg": "1994-01-01", 
        "description": "In this paper we present a linear time and space algorithm for constructing a visibility representation of a planar graph on an (\u230a3/2n\u230b\u22123)\u00d7(n\u22121) grid, thereby improving the previous bound of (2n\u22125)\u00d7(n\u22121). To this end we build in linear time the 4-block tree of a triangulated planar graph.", 
        "editor": [
          {
            "familyName": "Leeuwen", 
            "givenName": "Jan", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-57899-4_70", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-57899-4", 
            "978-3-540-48385-4"
          ], 
          "name": "Graph-Theoretic Concepts in Computer Science", 
          "type": "Book"
        }, 
        "name": "A more compact visibility representation", 
        "pagination": "411-424", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-57899-4_70"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "3d2aaa81e2b2af7afe93e8b9cbd5552737d38f59b25d841870079c18fad15ba2"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1012839777"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-57899-4_70", 
          "https://app.dimensions.ai/details/publication/pub.1012839777"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T15:06", 
        "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_8672_00000022.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-57899-4_70"
      }
    ]
     

    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/3-540-57899-4_70'

    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/3-540-57899-4_70'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57899-4_70'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-57899-4_70'


     

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

    87 TRIPLES      22 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-57899-4_70 schema:author Ncfd975bcd4524cb9914f44e28c3a3605
    2 schema:citation sg:pub.10.1007/3-540-57899-4_69
    3 sg:pub.10.1007/bf02187705
    4 sg:pub.10.1007/bf02187706
    5 https://doi.org/10.1016/0196-6774(86)90029-5
    6 https://doi.org/10.1109/31.34669
    7 https://doi.org/10.1109/sfcs.1991.185451
    8 https://doi.org/10.1109/sfcs.1992.267814
    9 https://doi.org/10.1137/0202012
    10 https://doi.org/10.1137/0214017
    11 schema:datePublished 1994
    12 schema:datePublishedReg 1994-01-01
    13 schema:description In this paper we present a linear time and space algorithm for constructing a visibility representation of a planar graph on an (⌊3/2n⌋−3)×(n−1) grid, thereby improving the previous bound of (2n−5)×(n−1). To this end we build in linear time the 4-block tree of a triangulated planar graph.
    14 schema:editor N2b9a7053dbce4c6887564980ec9d8df9
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf Nfca26857d25f4e01b6b61960bb821664
    19 schema:name A more compact visibility representation
    20 schema:pagination 411-424
    21 schema:productId N2552040d3c4f4fa1b2ea261667b51a2b
    22 Na6dffb34333d4e838c48ad6f2eee593d
    23 Nc3e732c8175447a79308d3d4afa64a8b
    24 schema:publisher N62cd41f25a474d4db1d483cf8cc9d582
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012839777
    26 https://doi.org/10.1007/3-540-57899-4_70
    27 schema:sdDatePublished 2019-04-15T15:06
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N7efbe9a617ce4a94baf477c137f85272
    30 schema:url http://link.springer.com/10.1007/3-540-57899-4_70
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N2552040d3c4f4fa1b2ea261667b51a2b schema:name doi
    35 schema:value 10.1007/3-540-57899-4_70
    36 rdf:type schema:PropertyValue
    37 N2b9a7053dbce4c6887564980ec9d8df9 rdf:first Nb55790a7d0d149f88664ee02da1a39b5
    38 rdf:rest rdf:nil
    39 N62cd41f25a474d4db1d483cf8cc9d582 schema:location Berlin, Heidelberg
    40 schema:name Springer Berlin Heidelberg
    41 rdf:type schema:Organisation
    42 N7efbe9a617ce4a94baf477c137f85272 schema:name Springer Nature - SN SciGraph project
    43 rdf:type schema:Organization
    44 Na6dffb34333d4e838c48ad6f2eee593d schema:name readcube_id
    45 schema:value 3d2aaa81e2b2af7afe93e8b9cbd5552737d38f59b25d841870079c18fad15ba2
    46 rdf:type schema:PropertyValue
    47 Nb55790a7d0d149f88664ee02da1a39b5 schema:familyName Leeuwen
    48 schema:givenName Jan
    49 rdf:type schema:Person
    50 Nc3e732c8175447a79308d3d4afa64a8b schema:name dimensions_id
    51 schema:value pub.1012839777
    52 rdf:type schema:PropertyValue
    53 Ncfd975bcd4524cb9914f44e28c3a3605 rdf:first sg:person.013743554756.94
    54 rdf:rest rdf:nil
    55 Nfca26857d25f4e01b6b61960bb821664 schema:isbn 978-3-540-48385-4
    56 978-3-540-57899-4
    57 schema:name Graph-Theoretic Concepts in Computer Science
    58 rdf:type schema:Book
    59 sg:person.013743554756.94 schema:affiliation https://www.grid.ac/institutes/grid.5477.1
    60 schema:familyName Kant
    61 schema:givenName Goos
    62 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013743554756.94
    63 rdf:type schema:Person
    64 sg:pub.10.1007/3-540-57899-4_69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018910920
    65 https://doi.org/10.1007/3-540-57899-4_69
    66 rdf:type schema:CreativeWork
    67 sg:pub.10.1007/bf02187705 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027312329
    68 https://doi.org/10.1007/bf02187705
    69 rdf:type schema:CreativeWork
    70 sg:pub.10.1007/bf02187706 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008881195
    71 https://doi.org/10.1007/bf02187706
    72 rdf:type schema:CreativeWork
    73 https://doi.org/10.1016/0196-6774(86)90029-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012551211
    74 rdf:type schema:CreativeWork
    75 https://doi.org/10.1109/31.34669 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061153032
    76 rdf:type schema:CreativeWork
    77 https://doi.org/10.1109/sfcs.1991.185451 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086324361
    78 rdf:type schema:CreativeWork
    79 https://doi.org/10.1109/sfcs.1992.267814 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086359610
    80 rdf:type schema:CreativeWork
    81 https://doi.org/10.1137/0202012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841200
    82 rdf:type schema:CreativeWork
    83 https://doi.org/10.1137/0214017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841806
    84 rdf:type schema:CreativeWork
    85 https://www.grid.ac/institutes/grid.5477.1 schema:alternateName Utrecht University
    86 schema:name Dept. of Computer Science, Utrecht University, Padualaan 14, 3584 CH Utrecht, the Netherlands
    87 rdf:type schema:Organization
     




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


    ...