Mathematics – Combinatorics
Scientific paper
2011-07-06
Mathematics
Combinatorics
42 pages, 25 figures; co-author added in replaced version
Scientific paper
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.
Boutin Debra L.
Cockburn Sally
Dean Alice
Margea Andrei
No associations
LandOfFree
Posets of Geometric Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Posets of Geometric Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Posets of Geometric Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-678166