Posets of geometric graphs


  • Debra L. Boutin Hamilton College, United States
  • Sally Cockburn Hamilton College, United States
  • Alice M. Dean Skidmore College, United States
  • Andrei M. Margea University of North Texas, United States




geometric graph, homomorphism, poset


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 Pn, Cn and Kn, as well as the Hasse diagrams of the geometric homomorphism posets (resp., Pn, Cn, Kn) of these graphs. The paper also provides the following results for general n: each of Pn and Cn has a unique minimal element and a unique maximal element; if kn then Pk (resp., Ck) is a subposet of Pn (resp., Cn); and Kn contains a chain of length n − 2.