KAIST Discrete Math Seminar

We show how to compute for n-vertex planar graphs in roughly O(n^11/6) expected time the diameter and the sum of the pairwise distances. These are the first algorithms for these problems using time O(n^c) for some constant c<2, even when restricted to undirected, unweighted planar graphs.

The Fibonacci dimension fdim(G) of a graph G is introduced as the smallest integer f such that G admits an isometric embedding into the f-dimensional Fibonacci cube. We will see combinatorial relations between the Fibonacci dimension and the isometric or lattice dimension, and establish the Fibonacci dimension for certain families of graphs. Finally, we will discuss the problem of computing the Fibonacci dimension, namely, its NP-hardness and approximation algorithms.

Joint work with D. Eppstein and S. Klavžar. Manuscript available at arxiv:0903.2507.