A Fast General Methodology for Information—Theoretically Optimal Encodings of Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999

AUTHORS

Xin He , Ming-Yang Kao , Hsueh-I Lu

ABSTRACT

We propose a fast methodology for encoding graphs with informationtheoretically minimum numbers of bits. The methodology is applicable to general classes of graphs; this paper focuses on simple planar graphs. Specifically, a graph with property π is called a π-graph. If π satisfies certain properties, then an n-node π-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2)X has at most β(n)+ o(β(n)) bits for any function β(n) = Ω (n) so that there are at most 2β(n)+ o(β(n)) distinct n-node π-graphs. Examples of such π include all conjunctions of the following sets of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; and (4) G has at most ℓ1 (respectively, ℓ2) distinct node (respectively, edge) labels. These examples are novel applications of small cycle separators of planar graphs and settle several problems that have been open since Tutte’s census series were published in 1960’s. More... »

PAGES

540-549

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48481-7_47

DOI

http://dx.doi.org/10.1007/3-540-48481-7_47

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, 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 and Engineering, 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 University06250, New Haven, CT, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, Yale University06250, 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, ROC", 
          "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, ROC"
          ], 
          "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": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "We propose a fast methodology for encoding graphs with informationtheoretically minimum numbers of bits. The methodology is applicable to general classes of graphs; this paper focuses on simple planar graphs. Specifically, a graph with property \u03c0 is called a \u03c0-graph. If \u03c0 satisfies certain properties, then an n-node \u03c0-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2)X has at most \u03b2(n)+ o(\u03b2(n)) bits for any function \u03b2(n) = \u03a9 (n) so that there are at most 2\u03b2(n)+ o(\u03b2(n)) distinct n-node \u03c0-graphs. Examples of such \u03c0 include all conjunctions of the following sets of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; and (4) G has at most \u21131 (respectively, \u21132) distinct node (respectively, edge) labels. These examples are novel applications of small cycle separators of planar graphs and settle several problems that have been open since Tutte\u2019s census series were published in 1960\u2019s.", 
    "editor": [
      {
        "familyName": "Ne\u0161et\u0159il", 
        "givenName": "Jaroslav", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48481-7_47", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66251-8", 
        "978-3-540-48481-3"
      ], 
      "name": "Algorithms - ESA\u2019 99", 
      "type": "Book"
    }, 
    "keywords": [
      "planar graphs", 
      "simple planar graph", 
      "general class", 
      "binary string x", 
      "graph G", 
      "certain properties", 
      "cycle separator", 
      "plane graph", 
      "general methodology", 
      "graph", 
      "optimal encoding", 
      "minimum number", 
      "property \u03c0", 
      "node labels", 
      "fast methodology", 
      "set of properties", 
      "string x", 
      "methodology", 
      "properties", 
      "problem", 
      "novel application", 
      "class", 
      "bits", 
      "set", 
      "applications", 
      "function", 
      "encoding", 
      "number", 
      "labels", 
      "information", 
      "example", 
      "conjunction", 
      "separator", 
      "time", 
      "series", 
      "paper", 
      "satisfies certain properties", 
      "node \u03c0", 
      "distinct node (respectively, edge) labels", 
      "small cycle separators", 
      "Tutte\u2019s census series", 
      "\u2019s census series", 
      "Fast General Methodology"
    ], 
    "name": "A Fast General Methodology for Information\u2014Theoretically Optimal Encodings of Graphs", 
    "pagination": "540-549", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006627258"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48481-7_47"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48481-7_47", 
      "https://app.dimensions.ai/details/publication/pub.1006627258"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_303.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48481-7_47"
  }
]
 

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-48481-7_47'

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-48481-7_47'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48481-7_47'

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-48481-7_47'


 

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

123 TRIPLES      23 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48481-7_47 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N53ad833a3eac4c1589bf770e7cb09d46
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description We propose a fast methodology for encoding graphs with informationtheoretically minimum numbers of bits. The methodology is applicable to general classes of graphs; this paper focuses on simple planar graphs. Specifically, a graph with property π is called a π-graph. If π satisfies certain properties, then an n-node π-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2)X has at most β(n)+ o(β(n)) bits for any function β(n) = Ω (n) so that there are at most 2β(n)+ o(β(n)) distinct n-node π-graphs. Examples of such π include all conjunctions of the following sets of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; and (4) G has at most ℓ1 (respectively, ℓ2) distinct node (respectively, edge) labels. These examples are novel applications of small cycle separators of planar graphs and settle several problems that have been open since Tutte’s census series were published in 1960’s.
7 schema:editor Nd64dc3a58b6d438faee0a56cd4bbd3e6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N5734bb4b5d2448e0ad06d62145eb2b31
12 schema:keywords Fast General Methodology
13 Tutte’s census series
14 applications
15 binary string x
16 bits
17 certain properties
18 class
19 conjunction
20 cycle separator
21 distinct node (respectively, edge) labels
22 encoding
23 example
24 fast methodology
25 function
26 general class
27 general methodology
28 graph
29 graph G
30 information
31 labels
32 methodology
33 minimum number
34 node labels
35 node π
36 novel application
37 number
38 optimal encoding
39 paper
40 planar graphs
41 plane graph
42 problem
43 properties
44 property π
45 satisfies certain properties
46 separator
47 series
48 set
49 set of properties
50 simple planar graph
51 small cycle separators
52 string x
53 time
54 ’s census series
55 schema:name A Fast General Methodology for Information—Theoretically Optimal Encodings of Graphs
56 schema:pagination 540-549
57 schema:productId N72b6b7a82e8f4471a20161a3e19673f2
58 N9b02a822e6a94005b11d5ddec46f7d31
59 schema:publisher N80fd1a88f69c4b79b70e93a5fda5ed47
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006627258
61 https://doi.org/10.1007/3-540-48481-7_47
62 schema:sdDatePublished 2022-01-01T19:17
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N334c856bb58b492181a31c7b4c2f6157
65 schema:url https://doi.org/10.1007/3-540-48481-7_47
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N06660dc1ceda43acb111bdb1aeb671d3 rdf:first sg:person.011536202643.55
70 rdf:rest Ndefc92115fb74e989f93653bc6cca616
71 N334c856bb58b492181a31c7b4c2f6157 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N53ad833a3eac4c1589bf770e7cb09d46 rdf:first sg:person.011352641523.42
74 rdf:rest N06660dc1ceda43acb111bdb1aeb671d3
75 N5734bb4b5d2448e0ad06d62145eb2b31 schema:isbn 978-3-540-48481-3
76 978-3-540-66251-8
77 schema:name Algorithms - ESA’ 99
78 rdf:type schema:Book
79 N72b6b7a82e8f4471a20161a3e19673f2 schema:name dimensions_id
80 schema:value pub.1006627258
81 rdf:type schema:PropertyValue
82 N80fd1a88f69c4b79b70e93a5fda5ed47 schema:name Springer Nature
83 rdf:type schema:Organisation
84 N937b6ca250154953acae16eeb23bd539 schema:familyName Nešetřil
85 schema:givenName Jaroslav
86 rdf:type schema:Person
87 N9b02a822e6a94005b11d5ddec46f7d31 schema:name doi
88 schema:value 10.1007/3-540-48481-7_47
89 rdf:type schema:PropertyValue
90 Nd64dc3a58b6d438faee0a56cd4bbd3e6 rdf:first N937b6ca250154953acae16eeb23bd539
91 rdf:rest rdf:nil
92 Ndefc92115fb74e989f93653bc6cca616 rdf:first sg:person.013345515575.46
93 rdf:rest rdf:nil
94 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
95 schema:name Mathematical Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
98 schema:name Pure Mathematics
99 rdf:type schema:DefinedTerm
100 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
101 schema:familyName He
102 schema:givenName Xin
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
104 rdf:type schema:Person
105 sg:person.011536202643.55 schema:affiliation grid-institutes:None
106 schema:familyName Kao
107 schema:givenName Ming-Yang
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011536202643.55
109 rdf:type schema:Person
110 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.412047.4
111 schema:familyName Lu
112 schema:givenName Hsueh-I
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
114 rdf:type schema:Person
115 grid-institutes:None schema:alternateName Department of Computer Science, Yale University06250, New Haven, CT, USA
116 schema:name Department of Computer Science, Yale University06250, New Haven, CT, USA
117 rdf:type schema:Organization
118 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
119 schema:name Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA
120 rdf:type schema:Organization
121 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan, ROC
122 schema:name Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan, ROC
123 rdf:type schema:Organization
 




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


...