On polygon numbers of circle graphs and distance hereditary graphs

Circle graphs are intersection graphs of chords in a circle and $k$-polygon graphs are the intersection graphs of chords in a convex $k$-sided polygon where each chord has its endpoints on distinct sides. Every $k$-polygon graph is a circle graph and every circle graph is a $k$-polygon graph for some $k$. The polygon number $\psi(G)$ of a circle graph $G$ is the minimum $k$ such that $G$ is a $k$-polygon graph and the polygon number of a circle representation is the minimum number of corners that must be added to the circle to produce a polygon representation. Given a circle graph $G$ and an integer $k$, determining whether $\psi(G) \le k$ is NP-complete, while the problem is solvable in polynomial time for fixed $k$, and the polygon number of a circle representation can be computed in polynomial time. In this paper, we give bounds on $\psi(G)$ when $G$ is an arbitrary circle graph -- upper bounds in terms of the independence number, the clique cover number, and the number of vertices of $G$, and a lower bound in terms of the asteroidal number of $G$ -- and show that $\psi(G)$ is equal to the asteroidal number of $G$ when $G$ is a connected nonclique distance hereditary graph. We then use our results to develop characterizations of distance hereditary permutation graphs. Finally, we describe linear time algorithms for finding the polygon number of a circle representation and for finding the asteroidal number of a distance hereditary graph, improvements over previously known algorithms for those problems.