Name
Abstract | ||
|---|---|---|
Ptolemaic graphs are graphs that satisfy the Ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs, and it is a natural generalization of block graphs (and hence trees). In this paper, a new characterization of ptolemaic graphs is presented. It is a laminar structure of cliques, and leads us to a canonical tree representation, which gives a simple intersection model for ptolemaic graphs. The tree representation is constructed in linear time from a perfect elimination ordering obtained by the lexicographic breadth first search. Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time. Using the tree representation, we also give an O(n) time algorithm for the Hamiltonian cycle problem. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11602613_20 | ISAAC |
Keywords | Field | DocType |
graph isomorphism,canonical tree representation,ptolemaic graph,tree representation,graph class,block graph,laminar structure,time algorithm,linear time,chordal graph,ptolemaic inequality,satisfiability,data structure,graph theory,hamiltonian cycle | Block graph,Discrete mathematics,Combinatorics,Indifference graph,Lexicographic breadth-first search,Clique-sum,Chordal graph,Trivially perfect graph,Pathwidth,Mathematics,Split graph | Conference |
Volume | ISSN | ISBN |
3827 | 0302-9743 | 3-540-30935-7 |
Citations | PageRank | References |
6 | 0.49 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ryuhei Uehara | 1 | 528 | 75.38 |
| yushi uno | 2 | 222 | 28.80 |