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


    ...