𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Edges and Kuratowski Subgraphs of Non-Planar Graphs

✍ Scribed by Jozef Širáň

Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
225 KB
Volume
113
Category
Article
ISSN
0025-584X

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved that any edge of a Pconnected non-planar graph G of order a t least 6 lies in a subdivision of K3,3 in G. For any 3-connected non-planar graph G of order a t least 6 we show that G contains at most four edges which belong to no subdivisions of K3,3 in G.

📜 SIMILAR VOLUMES

Covering genus-reducing edges by Kuratow
Covering genus-reducing edges by Kuratowski subgraphs
✍ Brunet, Richard; Richter, R. Bruce; ?ir�?, Jozef 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB

If G is a graph that minimally does not embed in a nonorientable surface, then each edge of G is in a subdivision of either K3.3 or K5. However, there is an example of a graph that minimally does not embed in the torus and some edge is in no subdivision of either K3.3 or K5.

Light subgraphs in planar graphs of mini
Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9
✍ B. Mohar; R. Škrekovski; H.-J. Voss 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

## Abstract A graph __H__ is light in a given class of graphs if there is a constant __w__ such that every graph of the class which has a subgraph isomorphic to __H__ also has a subgraph isomorphic to __H__ whose sum of degrees in __G__ is ≤ __w__. Let $\cal G$ be the class of simple planar graphs

A short proof of Kuratowski's graph plan
A short proof of Kuratowski's graph planarity criterion
✍ Makarychev, Yury 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 2 views

We present a new short combinatorial proof of the sufficiency part of the well-known Kuratowski's graph planarity criterion. The main steps are to prove that for a minor minimal non-planar graph G and any edge xy: (1) G-x-y does not contain θ-subgraph; (2) G-x-y is homeomorphic to the circle; (3)

On planar intersection graphs with forbi
On planar intersection graphs with forbidden subgraphs
✍ János Pach; Micha Sharir 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract Let ${\cal C}$ be a family of __n__ compact connected sets in the plane, whose intersection graph $G({\cal C})$ has no complete bipartite subgraph with __k__ vertices in each of its classes. Then $G({\cal C})$ has at most __n__ times a polylogarithmic number of edges, where the exponent