Ptolemaic graph

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs.

A graph is Ptolemaic if and only if it obeys any of the following equivalent conditions:

Based on the characterization by oriented trees, Ptolemaic graphs can be recognized in linear time.