New results on ptolemaic graphs

In this paper, we analyze ptolemaic graphs for their properties as chordal graphs. First, two characterizations of ptolemaic graphs are proved. The first one is based on the reduced clique graph, a structure that was defined by Habib and Stacho (Habib and Stacho, 2012). In the second one, we simplify the characterization presented by Uehara and Uno (Uehara and Uno, 2009) with a new proof. Then, known subclasses of ptolemaic graphs are reviewed in terms of minimal vertex separators. We also define another subclass, the laminar chordal graphs, and we show that a hierarchy of ptolemaic graphs can be built based on characteristics of the minimal vertex separators in each subclass.