Pseudoline arrangement graphs: degree sequences and eccentricities

Abstract

A pseudoline arrangement graph is a planar graph induced by an embedding of a (simple) pseudoline arrangement. We study the corresponding graph realization problem and properties of pseudoline arrangement graphs. In the first part, we give a simple criterion based on the degree sequence that says whether a degree sequence will have a pseudoline arrangement graph as one of its realizations. In the second part, we study the eccentricities of vertices in such graphs. We observe that the diameter (maximum eccentricity of a vertex in the graph) of any pseudoline arrangement graph on $n$ pseudolines is $n-2$. Then we characterize the diametrical vertices (whose eccentricity is equal to the graph diameter) of pseudoline arrangement graphs. These results hold for line arrangement graphs as well.

23 pages