On polygon numbers of circle graphs and distance hereditary graphs

In this paper, we show that ψ(G) is always at least as large as the asteroidal number of G, and equal to the asteroidal number of G when G is a connected distance hereditary graph that is not a clique. This implies that the classes of distance hereditary permutation graphs and distance hereditary AT-free graphs are the same, and we give a forbidden subgraph characterization of that class. We also establish the following upper bounds: ψ(G) is at most the clique cover number of G if G is not a clique, at most 1 plus the independence number of G, and at most ⌈n∕2⌉ where n≥3 is the number of vertices of G. Our results lead to linear time algorithms for finding the minimum number of corners that must be added to a given circle representation to produce a polygon representation, and for finding the asteroidal number of a distance hereditary graph, both of which are improvements over previous algorithms for those problems.