Compact encodings of planar graphs via canonical orderings and multiple parentheses View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1998

AUTHORS

Richie Chih-Nan Chuang , Ashim Garg , Xin He , Ming-Yang Kao , Hsueh-I Lu

ABSTRACT

We consider the problem of coding planar graphs by binary strings. Depending on whether O(1)-time queries for adjacency and degree are supported, we present three sets of coding schemes which all take linear time for encoding and decoding. The encoding lengths are significantly shorter than the previously known results in each case. More... »

PAGES

118-129

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0055046

DOI

http://dx.doi.org/10.1007/bfb0055046

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chuang", 
        "givenName": "Richie Chih-Nan", 
        "id": "sg:person.010000602234.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010000602234.32"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, 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": "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Xin", 
        "id": "sg:person.011352641523.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Yale University, 06250, New Haven, CT, USA", 
          "id": "http://www.grid.ac/institutes/grid.47100.32", 
          "name": [
            "Department of Computer Science, Yale University, 06250, New Haven, CT, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kao", 
        "givenName": "Ming-Yang", 
        "id": "sg:person.011536202643.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011536202643.55"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "We consider the problem of coding planar graphs by binary strings. Depending on whether O(1)-time queries for adjacency and degree are supported, we present three sets of coding schemes which all take linear time for encoding and decoding. The encoding lengths are significantly shorter than the previously known results in each case.", 
    "editor": [
      {
        "familyName": "Larsen", 
        "givenName": "Kim G.", 
        "type": "Person"
      }, 
      {
        "familyName": "Skyum", 
        "givenName": "Sven", 
        "type": "Person"
      }, 
      {
        "familyName": "Winskel", 
        "givenName": "Glynn", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0055046", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64781-2", 
        "978-3-540-68681-1"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "cases", 
      "degree", 
      "time", 
      "length", 
      "results", 
      "encoding", 
      "problem", 
      "parentheses", 
      "set", 
      "strings", 
      "adjacency", 
      "queries", 
      "graph", 
      "scheme", 
      "ordering", 
      "planar graphs", 
      "compact encoding", 
      "binary strings", 
      "linear time", 
      "canonical ordering", 
      "multiple parentheses"
    ], 
    "name": "Compact encodings of planar graphs via canonical orderings and multiple parentheses", 
    "pagination": "118-129", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024449507"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0055046"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0055046", 
      "https://app.dimensions.ai/details/publication/pub.1024449507"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_319.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0055046"
  }
]
 

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/bfb0055046'

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/bfb0055046'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0055046'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0055046'


 

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

125 TRIPLES      23 PREDICATES      47 URIs      40 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0055046 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N1de90611673a4d708b1a5415a70e8008
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description We consider the problem of coding planar graphs by binary strings. Depending on whether O(1)-time queries for adjacency and degree are supported, we present three sets of coding schemes which all take linear time for encoding and decoding. The encoding lengths are significantly shorter than the previously known results in each case.
7 schema:editor N0ab06ccbe8fd475dabb2bce24afb5476
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N0b94e08f9e0f473586ac139b5b04aae5
12 schema:keywords adjacency
13 binary strings
14 canonical ordering
15 cases
16 compact encoding
17 degree
18 encoding
19 graph
20 length
21 linear time
22 multiple parentheses
23 ordering
24 parentheses
25 planar graphs
26 problem
27 queries
28 results
29 scheme
30 set
31 strings
32 time
33 schema:name Compact encodings of planar graphs via canonical orderings and multiple parentheses
34 schema:pagination 118-129
35 schema:productId N245980a62b4647f8998cd1415ed93549
36 N27d6305e9a004701b6dc3b1464b82c5c
37 schema:publisher N683fbb0a22534d5a9d605060d0dc03cc
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024449507
39 https://doi.org/10.1007/bfb0055046
40 schema:sdDatePublished 2021-11-01T18:55
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher Nd7e5cbd047e047f583f94d14d28f09d9
43 schema:url https://doi.org/10.1007/bfb0055046
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N0ab06ccbe8fd475dabb2bce24afb5476 rdf:first Na5d753612684400687a8c4f3af795684
48 rdf:rest Nd08f109546254da6996d24a554bb4d3d
49 N0b94e08f9e0f473586ac139b5b04aae5 schema:isbn 978-3-540-64781-2
50 978-3-540-68681-1
51 schema:name Automata, Languages and Programming
52 rdf:type schema:Book
53 N1de90611673a4d708b1a5415a70e8008 rdf:first sg:person.010000602234.32
54 rdf:rest N86824423012d4c7dad0059b17e299873
55 N245980a62b4647f8998cd1415ed93549 schema:name dimensions_id
56 schema:value pub.1024449507
57 rdf:type schema:PropertyValue
58 N27d6305e9a004701b6dc3b1464b82c5c schema:name doi
59 schema:value 10.1007/bfb0055046
60 rdf:type schema:PropertyValue
61 N5af30d062a4c4d7f905bb89a3a7207c6 rdf:first sg:person.011536202643.55
62 rdf:rest Ne3e8f0b73e0d4fac90ed16322b1bab6a
63 N683fbb0a22534d5a9d605060d0dc03cc schema:name Springer Nature
64 rdf:type schema:Organisation
65 N86824423012d4c7dad0059b17e299873 rdf:first sg:person.013377047435.30
66 rdf:rest Nc149ac4c1ffc4ef795978332b193d187
67 Na5d753612684400687a8c4f3af795684 schema:familyName Larsen
68 schema:givenName Kim G.
69 rdf:type schema:Person
70 Naf347466bd2042bc84b67063dcf2c286 schema:familyName Skyum
71 schema:givenName Sven
72 rdf:type schema:Person
73 Nb7a7a5e0d7be427baa6845c889e8afc7 schema:familyName Winskel
74 schema:givenName Glynn
75 rdf:type schema:Person
76 Nc149ac4c1ffc4ef795978332b193d187 rdf:first sg:person.011352641523.42
77 rdf:rest N5af30d062a4c4d7f905bb89a3a7207c6
78 Nd08f109546254da6996d24a554bb4d3d rdf:first Naf347466bd2042bc84b67063dcf2c286
79 rdf:rest Nf425ea7d12ac4c5b875e54be1fc95582
80 Nd7e5cbd047e047f583f94d14d28f09d9 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 Ne3e8f0b73e0d4fac90ed16322b1bab6a rdf:first sg:person.013345515575.46
83 rdf:rest rdf:nil
84 Nf425ea7d12ac4c5b875e54be1fc95582 rdf:first Nb7a7a5e0d7be427baa6845c889e8afc7
85 rdf:rest rdf:nil
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
90 schema:name Data Format
91 rdf:type schema:DefinedTerm
92 sg:person.010000602234.32 schema:affiliation grid-institutes:grid.412047.4
93 schema:familyName Chuang
94 schema:givenName Richie Chih-Nan
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010000602234.32
96 rdf:type schema:Person
97 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
98 schema:familyName He
99 schema:givenName Xin
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
101 rdf:type schema:Person
102 sg:person.011536202643.55 schema:affiliation grid-institutes:grid.47100.32
103 schema:familyName Kao
104 schema:givenName Ming-Yang
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011536202643.55
106 rdf:type schema:Person
107 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.412047.4
108 schema:familyName Lu
109 schema:givenName Hsueh-I
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
111 rdf:type schema:Person
112 sg:person.013377047435.30 schema:affiliation grid-institutes:grid.273335.3
113 schema:familyName Garg
114 schema:givenName Ashim
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013377047435.30
116 rdf:type schema:Person
117 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
118 schema:name Department of Computer Science, State University of New York at Buffalo, 14260, Buffalo, NY, USA
119 rdf:type schema:Organization
120 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan
121 schema:name Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan
122 rdf:type schema:Organization
123 grid-institutes:grid.47100.32 schema:alternateName Department of Computer Science, Yale University, 06250, New Haven, CT, USA
124 schema:name Department of Computer Science, Yale University, 06250, New Haven, CT, USA
125 rdf:type schema:Organization
 




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


...