Posets of geometric graphs

Debra L. Boutin, Sally Cockburn, Alice M. Dean, Andrei M. Margea


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.


geometric graph, homomorphism, poset

Full Text:


DOI: https://doi.org/10.26493/1855-3974.212.563

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications