.
"Hsueh-I" .
.
"540-549" .
_:Nb34d80bba3f449388c7ab10bf6d44c09 "doi" .
.
"Xin" .
"general class" .
.
"Department of Computer Science, Yale University06250, New Haven, CT, USA" .
"set" .
.
"Ming-Yang" .
_:Nd32e9f5cc17249d7866d224c605ba25b .
"simple planar graph" .
"paper" .
_:N3940eeb8e0e441f8a88b576c38f59eab .
_:N772b6f361f22463783fbace2f2bede2f .
"general methodology" .
"optimal encoding" .
"cycle separator" .
"labels" .
_:N4fc88089ac874f5e9f4b7c0127021113 "Jaroslav" .
"graph" .
"separator" .
"methodology" .
_:N6f803c3f18df4ae8aa586bc5410a4f97 "pub.1006627258" .
_:N6f803c3f18df4ae8aa586bc5410a4f97 "dimensions_id" .
"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." .
_:Nae83d4c013af4afa9968e80b572a94a0 .
"chapter" .
.
.
_:N3ed3e8e5bb7340ea876ee88ab21eee27 .
_:N4b4fd0caf5454af6bae8f3bff7d927bc .
_:N4b4fd0caf5454af6bae8f3bff7d927bc .
.
_:N4fc88089ac874f5e9f4b7c0127021113 "Ne\u0161et\u0159il" .
"certain properties" .
"class" .
"time" .
_:Nae83d4c013af4afa9968e80b572a94a0 "Algorithms - ESA\u2019 99" .
"A Fast General Methodology for Information\u2014Theoretically Optimal Encodings of Graphs" .
"conjunction" .
"chapters" .
_:N6f803c3f18df4ae8aa586bc5410a4f97 .
"applications" .
"properties" .
"Tutte\u2019s census series" .
_:N6f803c3f18df4ae8aa586bc5410a4f97 .
"node \u03C0" .
_:N3940eeb8e0e441f8a88b576c38f59eab .
"problem" .
.
"minimum number" .
"2022-01-01T19:17" .
"small cycle separators" .
"plane graph" .
"bits" .
"node labels" .
"\u2019s census series" .
"true"^^ .
"Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA" .
_:N24f1fcf69cc64b43a2e3934dc4b585b5 .
"set of properties" .
.
_:Nb34d80bba3f449388c7ab10bf6d44c09 "10.1007/3-540-48481-7_47" .
.
.
"distinct node (respectively, edge) labels" .
"Lu" .
"https://scigraph.springernature.com/explorer/license/" .
"planar graphs" .
"https://doi.org/10.1007/3-540-48481-7_47" .
"novel application" .
"Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan, ROC" .
_:N4fc88089ac874f5e9f4b7c0127021113 .
_:N3ed3e8e5bb7340ea876ee88ab21eee27 _:N772b6f361f22463783fbace2f2bede2f .
"satisfies certain properties" .
"function" .
_:N24f1fcf69cc64b43a2e3934dc4b585b5 .
_:Nd32e9f5cc17249d7866d224c605ba25b .
"He" .
"encoding" .
_:Nae83d4c013af4afa9968e80b572a94a0 .
.
.
_:N3940eeb8e0e441f8a88b576c38f59eab _:N4fc88089ac874f5e9f4b7c0127021113 .
.
"Department of Computer Science, Yale University06250, New Haven, CT, USA" .
"information" .
_:Nb34d80bba3f449388c7ab10bf6d44c09 .
_:N772b6f361f22463783fbace2f2bede2f .
.
"string x" .
"en" .
.
_:Nb34d80bba3f449388c7ab10bf6d44c09 .
"graph G" .
"1999-01-01" .
_:Nae83d4c013af4afa9968e80b572a94a0 "978-3-540-66251-8" .
"binary string x" .
.
"Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY, USA" .
_:Nd32e9f5cc17249d7866d224c605ba25b "Springer Nature - SN SciGraph project" .
"property \u03C0" .
"Mathematical Sciences" .
"fast methodology" .
"Fast General Methodology" .
"number" .
_:Nae83d4c013af4afa9968e80b572a94a0 "978-3-540-48481-3" .
"example" .
"Kao" .
"1999" .
.
"Pure Mathematics" .
"series" .
.
_:N24f1fcf69cc64b43a2e3934dc4b585b5 _:N3ed3e8e5bb7340ea876ee88ab21eee27 .
"Department of Computer Science and Information Engineering, National Chung-Cheng University, 621, Chia-Yi, Taiwan, ROC" .
.
.
_:N4b4fd0caf5454af6bae8f3bff7d927bc "Springer Nature" .