✦ LIBER ✦

A criterion for the planarity of a graph

✍ Scribed by Jerome R. Breitenbach

Publisher: John Wiley and Sons
Year: 1986
Tongue: English
Weight: 146 KB
Volume: 10
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190100411

No coin nor oath required. For personal study only.

✦ Synopsis

In a recent paper, Carsten Thomassen [Carsten Thomassen, Planarity and duality of finite and infinite graphs. J. Combinatorial Theory Ser. B 29 (1980) 244-2711 has shown that a number of criteria for the planarity of a graph can be reduced to that of Kuratowski. Here we present another criterion which, as well, is easily proved via Kuratowski's. The criterion is based on the observation that the imbedding of a graph in a plane imposes a cyclic ordering, say clockwise, on the edges incident with each vertex, and that these cyclic orderings are related.

📜 SIMILAR VOLUMES

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)

A new planarity criterion for 3-connecte

A new planarity criterion for 3-connected graphs

✍ Alexander K. Kelmans 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB

## Abstract Direct proofs of some planarity criteria are presented.

A reduction criterion for supereulerian

A reduction criterion for supereulerian graphs

✍ Catlin, Paul A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 1 views

Let G be a graph, and let H be a connected subgraph of G. When it is known that the graph G/H (obtained from G by contracting H to a vertex) has a spanning eulerian subgraph, under what conditions can it be inferred that G itself has a spanning eulerian subgraph? 0 1996 John Wiley & Sons, Inc.

A GRASP for graph planarization

✍ Resende, Mauricio G. C.; Ribeiro, Celso C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB 👁 2 views

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describe a GRASP for the graph planarization problem, extending the heuristic of Goldschmidt and Takvorian [ Networks 24 (1994) 69-73]. We review the basic concepts of GRASP: co

Coloring the square of a planar graph

✍ Jan van den Heuvel; Sean McGuinness 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB

## Abstract We prove that for any planar graph __G__ with maximum degree Δ, it holds that the chromatic number of the square of __G__ satisfies χ(__G__^2^) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002

On the linear vertex-arboricity of a pla

On the linear vertex-arboricity of a planar graph

✍ K. S. Poh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB 👁 1 views

## Abstract We prove in this note that the linear vertex‐arboricity of any planar graph is at most three, which confirms a conjecture due to Broere and Mynhardt, and others.