Posets of geometric graphs
Debra Boutin, Sally Cockburn, Alice M. Dean, Andrei Margea · Ars Mathematica Contemporanea · 2012
A geometric graph Ḡ is a simple graph drawn in the plane, on points in general position, with straight-line edges. We call Ḡ a geometric realization of the underlying abstract graph G . A geometric homomorphism f : Ḡ → ̄H is a vertex map that preserves adjacencies and crossings (but not necessarily non-adjacencies or non-crossings). This work uses geometric homomorphisms to introduce a partial order on the set of isomorphism classes of geometric realizations of an abstract graph G . Set Ḡ ≼ Ĝ if Ḡ and Ĝ are geometric realizations of G and there is a vertex-injective geometric homomorphism f : Ḡ → Ĝ . This paper develops tools to determine when two geometric realizations are comparable. Further, for 3 ≤ n ≤ 6, this paper provides the isomorphism classes of geometric realizations of P n , C n and K n , as well as the Hasse diagrams of the geometric homomorphism posets (resp., P n , C n , K n ) of these graphs. The paper also provides the following results for general n : each of P n and C n has a unique minimal element and a unique maximal element; if k ≤ n then P k (resp., C k ) is a subposet of P n (resp., C n ); and K n contains a chain of length n − 2.