Characterizing planarity using theta graphs

DOI10.1002/(SICI)1097-0118(199801)27:1%3C17::AID-JGT4%3E3.0.CO;2-JMaRDI QIDQ4376501zbMATH OpenOpenAlexFDO

Authors Jozef Širáň, Dan S. Archdeacon

Publication date 28 April 1998

Full work available at URL https://doi.org/10.1002/(sici)1097-0118(199801)27:1%3C17::aid-jgt4%3E3.0.co;2-j

zbMATH Keywords

planar graphsigned graphtheta graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Review text

The authors give a characterization of planar graphs in terms of their claws (= three half-edges incident with a common vertex) and their theta graphs (= subhomeomorphs of \(K_{2,3}\)). Specifically, one begins by choosing local rotations for all the claws in a graph. Such a choice is consistent if each theta subgraph can be embedded in the plane so that the edges of its two claws are oriented according to the given local rotation. The main theorem: a graph is planar if and only if it admits a consistent choice of local rotations for its claws. Furthermore, one can begin with an arbitrary choice of local rotations for the claws, and determine whether there is a consistent choice by considering a certain graph whose vertices correspond to the claws of the given graph and whose edges correspond to its theta subgraphs.

Recommendations

• Another characterisation of planar graphs
• scientific article; zbMATH DE number 431506
• scientific article; zbMATH DE number 4135992
• A characterization of projective-planar signed graphs
• On Boolean characterizations of planarity and planar embeddings of graphs

Cited in

(3)

• A characterization of projective-planar signed graphs
• Sewing ribbons on graphs in space
• AN ENUMERATION OF THETA-CURVES WITH UP TO SEVEN CROSSINGS

This page was built for publication: Characterizing planarity using theta graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376501)