Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Entire DC Network
A Tree Representation For P4-Sparse Graphs, B. Jamison, Stephan Olariu
A Tree Representation For P4-Sparse Graphs, B. Jamison, Stephan Olariu
Computer Science Faculty Publications
A graph G is P4-sparse if no set of five vertices in G induces more than one chordless path of length three. P4-sparse graphs generalize both the class of cographs and the class of P4-reducible graphs. We give several characterizations for P4-sparse graphs and show that they can be constructed from single-vertex graphs by a finite sequence of operations. Our characterization implies that the P4-sparse graphs admit a tree representation unique up to isomorphism. Furthermore, this tree representation can be obtained in polynomial time.
A Charming Class Of Perfectly Orderable Graphs, Chinh T. Hoang, Frederic Maffray, Stephan Olariu, Myriam Preissmann
A Charming Class Of Perfectly Orderable Graphs, Chinh T. Hoang, Frederic Maffray, Stephan Olariu, Myriam Preissmann
Computer Science Faculty Publications
We investigate the following conjecture of Vašek Chvátal: any weakly triangulated graph containing no induced path on five vertices is perfectly orderable. In the process we define a new polynomially recognizable class of perfectly orderable graphs called charming. We show that every weakly triangulated graph not containing as an induced subgraph a path on five vertices or the complement of a path on six vertices is charming.
On Sources In Comparability Graphs, With Applications, Stephan Olariu
On Sources In Comparability Graphs, With Applications, Stephan Olariu
Computer Science Faculty Publications
We characterize sources in comparability graphs and show that our result provides a unifying look at two recent results about interval graphs.
The Morphology Of Convex Polygons, Stephan Olariu
The Morphology Of Convex Polygons, Stephan Olariu
Computer Science Faculty Publications
A simple polygon P is said to be unimodal if for every vertex of P, the Euclidian distance function to the other vertices of P is unimodal. The study of unimodal polygons has emerged as a fruitful area of computational and discrete geometry. We study unimodality properties of a number of special convex polygons from the morphological point of view. In particular, we establish a hierarchy among three classes of convex polygons in terms of their unimodality properties.