✦ LIBER ✦

A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs

✍ Scribed by Dale J. Skrien

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 319 KB
Volume: 6
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190060307

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Given a set F of digraphs, we say a graph G is a F‐graph (resp., F*‐graph) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in F. It is proved that all the classes of graphs mentioned in the title are F‐graphs or F*‐graphs for subsets F of a set of three digraphs.

📜 SIMILAR VOLUMES

Efficient algorithms for interval graphs

Efficient algorithms for interval graphs and circular-arc graphs

✍ U. I. Gupta; D. T. Lee; J. Y.-T. Leung 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 476 KB

## Abstract We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in __O__(__n__ log __n__) time [__O__(__n__) time if the endpoints of the

Metric characterizations of proper inter

Metric characterizations of proper interval graphs and tree-clique graphs

✍ Gutierrez, M.; Oubi�a, L. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB 👁 2 views

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real

Interval bigraphs and circular arc graph

Interval bigraphs and circular arc graphs

✍ Pavol Hell; Jing Huang 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB

## Abstract We prove that the complements of interval bigraphs are precisely those circular arc graphs of clique covering number two, which admit a representation without two arcs covering the whole circle. We give another characterization of interval bigraphs, in terms of a vertex ordering, that w

On partitioning interval graphs into pro

On partitioning interval graphs into proper interval subgraphs and related problems

✍ Frédéric Gardi 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

In this paper, we establish that any interval graph (resp. circulararc graph) with n vertices admits a partition into at most log 3 n (resp. log 3 n +1) proper interval subgraphs, for n>1. The proof is constructive and provides an efficient algorithm to compute such a partition. On the other hand, t

Efficient algorithms for centers and med

Efficient algorithms for centers and medians in interval and circular-arc graphs

✍ Sergei Bespamyatnikh; Binay Bhattacharya; Mark Keil; David Kirkpatrick; Michael 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 267 KB

## Abstract The __p__‐center problem is to locate __p__ facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The __p__‐median problem is to locate __p__ facilities on a network so as to minimize the average distance from a demand point to its c

Solving the all-pair shortest path query

Solving the all-pair shortest path query problem on interval and circular-arc graphs

✍ Chen, Danny Z.; Lee, D. T.; Sridhar, R.; Sekharan, Chandra N. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 3 views

In this paper, we study the following all-pair shortest path query problem: Given the interval model of an unweighted interval graph of n vertices, build a data structure such that each query on the shortest path (or its length) between any pair of vertices of the graph can be processed efficiently