𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Characterization and algorithms of curve map graphs

✍ Scribed by Fǎnicǎ Gavril; Johanan Schönheim

Publisher
Elsevier Science
Year
1982
Tongue
English
Weight
685 KB
Volume
4
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Classes and Recognition of Curve Contact
Classes and Recognition of Curve Contact Graphs
✍ Petr Hliněný 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 737 KB

Contact graphs are a special kind of intersection graphs of geometrical objects in which the objects are not allowed to cross but only to touch each other. Contact graphs of simple curves, and line segments as a special case, in the plane are considered. Various classes of contact graphs are introdu

Transversal hypergraphs to perfect match
Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
✍ Endre Boros; Khaled Elbassioni; Vladimir Gurvich 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers

The coverse of the Jordan Curve Theorem
The coverse of the Jordan Curve Theorem and a characterization of planar maps
✍ Carsten Thomassen 📂 Article 📅 1989 🏛 Springer 🌐 English ⚖ 255 KB

We show that a compact set F in the plane R 2 is the union of boundaries of a map if and only if each point of F is on the boundary of at least two arcwise connected components of R2\F, and it is accessible from each of those components.

Interval graphs and maps of DNA
Interval graphs and maps of DNA
✍ Michael S. Waterman; Jerrold R. Griggs 📂 Article 📅 1986 🏛 Springer 🌐 English ⚖ 348 KB

A special class of interval graphs is defined and characterized, and an algorithm is given for their construction. These graphs are motivated by an important representation of DNA called restriction maps by molecular biologists. Circular restriction maps are easily included.