𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Recognition of Circle Graphs

✍ Scribed by J. Spinrad

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
736 KB
Volume
16
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

This paper presents a new algorithm for recognizing circle graphs, combining ideas from an earlier circle graph recognition algorithm due to Gabor, Hsu, and Supowit and an algorithm to determine whether a graph can be decomposed by the split decomposition. The result is an (O\left(n^{2}\right)) algorithm for placing chords on the circle when the split decomposition is known. When combined with the result of the companion paper, this gives an (O\left(n^{2}\right)) algorithm for circle graph recognition. (1) 1994 Academic Press, Inc.

📜 SIMILAR VOLUMES

Orientations of circle graphs
Orientations of circle graphs
✍ R. C. Read; D. Rotem; J. Urrutia 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 756 KB
Unimodularity and circle graphs
Unimodularity and circle graphs
✍ André Bouchet 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 309 KB

A property of unimodularity is introduced for antisymmetric integral matrices. It is satisfied by the adjacency matrix of a circle graph provided with a Naji orientation . In a further paper we shall interprete this result in terms of symmetric matroids introduced in . In this communication we give

Circle graph obstructions under pivoting
Circle graph obstructions under pivoting
✍ Jim Geelen; Sang-il Oum 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 331 KB

## Abstract A circle graph is the intersection graph of a set of chords of a circle. The class of circle graphs is closed under pivot‐minors. We determine the pivot‐minor‐minimal non‐circle‐graphs; there are 15 obstructions. These obstructions are found, by computer search, as a corollary to Bouche

Excluding a bipartite circle graph from
Excluding a bipartite circle graph from line graphs
✍ Sang-il Oum 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 215 KB

## Abstract We prove that, for a fixed bipartite circle graph __H__, all line graphs with sufficiently large rank‐width (or clique‐width) must have a pivot‐minor isomorphic to __H__. To prove this, we introduce graphic delta‐matroids. Graphic delta‐matroids are minors of delta‐matroids of line grap

Polygon Graph Recognition
Polygon Graph Recognition
✍ E.S. Elmallah; L.K. Stewart 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 335 KB

For any fixed integer k G 2, define the class of k-polygon graphs as the intersection graphs of chords inside a convex k-polygon, where the endpoints of each chord lie on two different sides. The case where k s 2 is degenerate; for our purpose, we view any pair of parallel lines as a 2-polygon. Henc