Posets of geometric graphs

DOI10.26493/1855-3974.212.563MaRDI QIDQ4906177zbMATH OpenOpenAlexWikidataFDO

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

Publication date 7 February 2013

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.1131

zbMATH Keywords

geometric graphhomomorphismposet.

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Partial orders, general (06A06)

Abstract: A geometric graph G(bar) is a simple graph drawn in the plane, on points in general position, with straight-line edges. We call G(bar) a geometric realization of the underlying abstract graph G. A geometric homomorphism 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. We say G(bar) precedes G(hat) if G(bar) and G(hat) are geometric realizations of G and there is a vertex-injective geometric homomorphism from G(bar) to G(hat). This paper develops tools to determine when two geometric realizations are comparable. Further, for 3 leq n leq 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 of these graphs. The paper also provides the following results for general n: the poset of P_n and C_n has a unique minimal element and a unique maximal element; if k leq n then the poset of P_k (resp., the poset of C_k) is a subposet of the poset for P_n (resp., C_n); and the poset for K_n contains a chain of length n-2.

Recommendations

• The homomorphism poset of \(K_{2,n}\)
• Homomorphic preimages of geometric paths
• Geometric graph homomorphisms
• Homomorphic Preimages of Geometric Cycles
• scientific article; zbMATH DE number 1342089

Cited in

(6)

• Homomorphic preimages of geometric paths
• The homomorphism poset of \(K_{2,n}\)
• Geometric graph homomorphisms
• scientific article; zbMATH DE number 5949787 (Why is no real title available?)
• scientific article; zbMATH DE number 15259 (Why is no real title available?)
• scientific article; zbMATH DE number 7157680 (Why is no real title available?)

This page was built for publication: Posets of geometric graphs

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