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 N75d64a2558a34406870a1ea115c7372c
    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 N12b4b27264f143b69c76016088246218
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf Nb9578f9bd66b48fe9229e1dfbd385a4a
    19 schema:name A more compact visibility representation
    20 schema:pagination 411-424
    21 schema:productId N552a097c29f14bb9a936ee1b48784c56
    22 N6b6e714efa60406ba4433c657cee786a
    23 Nd672c404a9f84a41841879d42e73a8b7
    24 schema:publisher N7fefc9beab0a4af9809fe9be8ff5940c
    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 Ne64d7b57b6e643d886bb139891fd64a2
    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 N12b4b27264f143b69c76016088246218 rdf:first N5de985daf66f424186ee4d6c128e246e
    35 rdf:rest rdf:nil
    36 N552a097c29f14bb9a936ee1b48784c56 schema:name readcube_id
    37 schema:value 3d2aaa81e2b2af7afe93e8b9cbd5552737d38f59b25d841870079c18fad15ba2
    38 rdf:type schema:PropertyValue
    39 N5de985daf66f424186ee4d6c128e246e schema:familyName Leeuwen
    40 schema:givenName Jan
    41 rdf:type schema:Person
    42 N6b6e714efa60406ba4433c657cee786a schema:name doi
    43 schema:value 10.1007/3-540-57899-4_70
    44 rdf:type schema:PropertyValue
    45 N75d64a2558a34406870a1ea115c7372c rdf:first sg:person.013743554756.94
    46 rdf:rest rdf:nil
    47 N7fefc9beab0a4af9809fe9be8ff5940c schema:location Berlin, Heidelberg
    48 schema:name Springer Berlin Heidelberg
    49 rdf:type schema:Organisation
    50 Nb9578f9bd66b48fe9229e1dfbd385a4a schema:isbn 978-3-540-48385-4
    51 978-3-540-57899-4
    52 schema:name Graph-Theoretic Concepts in Computer Science
    53 rdf:type schema:Book
    54 Nd672c404a9f84a41841879d42e73a8b7 schema:name dimensions_id
    55 schema:value pub.1012839777
    56 rdf:type schema:PropertyValue
    57 Ne64d7b57b6e643d886bb139891fd64a2 schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    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)


    ...