Geodesic
Posets of geometric graphs
Ars Mathematica Contemporanea, Tome 5 (2012) no. 2, pp. 269-288.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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 k ≤ n then Pk (resp., Ck) is a subposet of Pn (resp., Cn); and Kn contains a chain of length n − 2.
DOI : 10.26493/1855-3974.212.563
Keywords: geometric graph, homomorphism, poset 
@article{10_26493_1855_3974_212_563,
     author = {Debra L. Boutin and Sally Cockburn and Alice M. Dean and Andrei M. Margea},
     title = {Posets of geometric graphs},
     journal = {Ars Mathematica Contemporanea},
     pages = {269--288},
     publisher = {mathdoc},
     volume = {5},
     number = {2},
     year = {2012},
     doi = {10.26493/1855-3974.212.563},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.212.563/}
}
TY  - JOUR
AU  - Debra L. Boutin
AU  - Sally Cockburn
AU  - Alice M. Dean
AU  - Andrei M. Margea
TI  - Posets of geometric graphs
JO  - Ars Mathematica Contemporanea
PY  - 2012
SP  - 269
EP  - 288
VL  - 5
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.212.563/
DO  - 10.26493/1855-3974.212.563
LA  - en
ID  - 10_26493_1855_3974_212_563
ER  - 
%0 Journal Article
%A Debra L. Boutin
%A Sally Cockburn
%A Alice M. Dean
%A Andrei M. Margea
%T Posets of geometric graphs
%J Ars Mathematica Contemporanea
%D 2012
%P 269-288
%V 5
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.212.563/
%R 10.26493/1855-3974.212.563
%G en
%F 10_26493_1855_3974_212_563
Debra L. Boutin; Sally Cockburn; Alice M. Dean; Andrei M. Margea. Posets of geometric graphs. Ars Mathematica Contemporanea, Tome 5 (2012) no. 2, pp. 269-288. doi : 10.26493/1855-3974.212.563. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.212.563/

Cité par Sources :