Planarity of Data Networks

Date Added: Jun 2011
Format: PDF

A planar graph is one that can be drawn (say on a piece of paper) without any crossing links. In this paper, the authors show, using a new data set, that data-network graphs show a surprisingly high likelihood of being planar. The data set - the Internet Topology Zoo - is a store of network data created from the information that network operators make public. As such, it includes meta-data that they could never have derived from automated network measurements. A surprising number of graphs in the Zoo are planar, many more than can be explained through the models for graph formation they tested. They speculate that planarity results from the requirement to build transparent networks that network operators can understand easily.