Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs

详细信息    查看全文

• 作者：Cyril Gavoille ; Arnaud Labourel
• 刊名：Lecture Notes in Computer Science
• 出版年：2007
• 出版时间：2007
• 年：2007
• 卷：4698
• 期：1
• 页码：582-593
• 全文大小：525 KB
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Implicit representation of graphs is a coding of the structure of graphs using distinct labels so that adjacency between any two vertices can be decided by inspecting their labels alone. All previous implicit representations of planar graphs were based on the classical three forests decomposition technique (a.k.a. Schnyder’s trees), yielding asymptotically to a 3logn-bit label representation where n is the number of vertices of the graph. We propose a new implicit representation of planar graphs using asymptotically 2logn-bit labels. As a byproduct we have an explicit construction of a graph with n 2 + o(1) vertices containing all n-vertex planar graphs as induced subgraph, the best previous size of such induced-universal graph was O(n 3).