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


Ontology type: schema:Chapter     


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": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66251-8", 
        "978-3-540-48481-3"
      ], 
      "name": "Algorithms - ESA\u2019 99", 
      "type": "Book"
    }, 
    "keywords": [
      "satisfies certain properties", 
      "simple planar graph", 
      "planar graphs", 
      "general class", 
      "general methodology", 
      "certain properties", 
      "optimal encoding", 
      "property \u03a0", 
      "graph", 
      "minimum number", 
      "node labels", 
      "set of properties", 
      "cycle separator", 
      "methodology", 
      "string x", 
      "graph G", 
      "problem", 
      "bits", 
      "class", 
      "fast methodology", 
      "novel application", 
      "plane graph", 
      "set", 
      "encoding", 
      "applications", 
      "properties", 
      "function", 
      "example", 
      "information", 
      "labels", 
      "number", 
      "conjunction", 
      "series", 
      "time", 
      "separator", 
      "paper", 
      "node \u03c0", 
      "binary string X", 
      "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": "2021-11-01T19:01", 
    "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_440.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 Na407541202744591946704e1f76a705c
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 Nafee2458426c4cbea78db72cc1a77851
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3e01c63444c242cca7a038e7d1f272c1
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 N00eb9cd1bcd54286aeb725cc9d6612d6
58 N0f440893dbae47269df546792ef50efc
59 schema:publisher N7bdb365e04da4aa281343c2695a6a26c
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 2021-11-01T19:01
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N55af2aeb55ab460aa98c23f5d42fff59
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 N00eb9cd1bcd54286aeb725cc9d6612d6 schema:name dimensions_id
70 schema:value pub.1006627258
71 rdf:type schema:PropertyValue
72 N0f440893dbae47269df546792ef50efc schema:name doi
73 schema:value 10.1007/3-540-48481-7_47
74 rdf:type schema:PropertyValue
75 N12138d7152024affbcfec3131a2a0327 rdf:first sg:person.013345515575.46
76 rdf:rest rdf:nil
77 N34213d14745f4577b3bbe33e369f6b15 schema:familyName Nešetřil
78 schema:givenName Jaroslav
79 rdf:type schema:Person
80 N3e01c63444c242cca7a038e7d1f272c1 schema:isbn 978-3-540-48481-3
81 978-3-540-66251-8
82 schema:name Algorithms - ESA’ 99
83 rdf:type schema:Book
84 N55af2aeb55ab460aa98c23f5d42fff59 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 N5e5a8dea1a974766a242b711fc2e1f19 rdf:first sg:person.011536202643.55
87 rdf:rest N12138d7152024affbcfec3131a2a0327
88 N7bdb365e04da4aa281343c2695a6a26c schema:name Springer Nature
89 rdf:type schema:Organisation
90 Na407541202744591946704e1f76a705c rdf:first sg:person.011352641523.42
91 rdf:rest N5e5a8dea1a974766a242b711fc2e1f19
92 Nafee2458426c4cbea78db72cc1a77851 rdf:first N34213d14745f4577b3bbe33e369f6b15
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)


...