Planarity of data networks

Abstract

A planar graph is one that can be drawn (say on a piece of paper) without any crossing links. In this paper we 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 we 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 we tested. We speculate that planarity results from the requirement to build transparent networks that network operators can understand easily.