The Arc-Width of a Graph

Abstract

The arc-representation of a graph is a mapping from the set of vertices to the arcs of a circle such that adjacent vertices are mapped to intersecting arcs. The width of such a representation is the maximum number of arcs having a point in common. The arc-width ($aw$) of a graph is the minimum width of its arc-representations. We show how arc-width is related to path-width and vortex-width. We prove that $aw(K_{s,s})=s$.