### Abstract

We propose a fast methodology for encoding graphs with information-theoretically 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 n-graphs. Examples of such n 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.

Original language | English (US) |
---|---|

Title of host publication | Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings |

Editors | Jaroslav Nešetřil |

Publisher | Springer Verlag |

Pages | 540-549 |

Number of pages | 10 |

ISBN (Print) | 3540662510, 9783540662518 |

DOIs | |

State | Published - Jan 1 1999 |

Event | 7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic Duration: Jul 16 1999 → Jul 18 1999 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1643 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 7th Annual European Symposium on Algorithms, ESA 1999 |
---|---|

Country | Czech Republic |

City | Prague |

Period | 7/16/99 → 7/18/99 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings*(pp. 540-549). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643). Springer Verlag. https://doi.org/10.1007/3-540-48481-7_47