Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 269–288
Posets of geometric graphs
Debra L. Boutin
Department of Mathematics, Hamilton College, Clinton, NY 13323, USA
Sally Cockburn
Department of Mathematics, Hamilton College, Clinton, NY 13323, USA
Alice M. Dean
Mathematics and Computer Science Department, Skidmore College
Saratoga Springs, NY 12866, USA
Andrei M. Margea
Department of Computer Science, University of Texas, Austin, TX 78712, USA
Received 3 June 2011, accepted 31 January 2012, published online 22 March 2012
Abstract
A geometric graphG is a simple graph drawn in the plane, on points in general position,
with straight-line edges. We callG a geometric realization of the underlying abstract graph
G. A geometric homomorphism f : G→ 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 G  Ĝ if G and Ĝ are geometric realizations of
G and there is a vertex-injective geometric homomorphism f : G → Ĝ. 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); andKn contains a chain of length n−2.
Keywords: Geometric graph, homomorphism, poset.
Math. Subj. Class.: 05C62, 06A06
E-mail addresses: dboutin@hamilton.edu (Debra L. Boutin), scockbur@hamilton.edu (Sally Cockburn),
adean@skidmore.edu (Alice M. Dean), utistu87@cs.utexas.edu (Andrei M. Margea)
Copyright c© 2012 DMFA Slovenije
270 Ars Math. Contemp. 5 (2012) 269–288
1 Introduction
The topic of graph homomorphisms has been a subject of growing interest; for an excellent
survey of the area see [9]. In [3], Boutin and Cockburn extend the theory of graph homo-
morphisms to geometric graphs. In this paper we use geometric homomorphisms to define
and study posets of geometric realizations of a given abstract graph. Throughout this work
the term graph means simple graph.
A geometric graph G is a graph drawn in the plane, on points in general position, with
straight-line edges. What we care about in a geometric graph is which pairs of vertices
are adjacent and which pairs of edges cross. Thus two geometric graphs will be called
isomorphic if there is a bijection between their vertex sets that preserves adjacencies, non-
adjacencies, crossings, and non-crossings. Note that there are other ways to define geomet-
ric graph isomorphism; this is discussed further in Section 2.
In [3], the definition of graph homomorphism was extended to the context of geometric
graphs in the following way. A geometric homomorphism is a vertex map f : G →
H that preserves both adjacencies and crossings (but not necessarily non-adjacencies or
non-crossings). If such a map exists we write G → H and say that G is (geometrically)
homomorphic to H . There are many similarities between abstract graph homomorphisms
and geometric graph homomorphisms, but there are also great contrasts. Results that are
straightforward in the context of abstract graphs can be complex in the context of geometric
graphs.
In abstract graph homomorphism theory, two vertices cannot be identified under any
homomorphism if and only if they are adjacent. However, in [3] we see that there are
additional reasons why two vertices cannot be identified under geometric homomorphism:
if they are involved in a common edge crossing; if they are endpoints of an odd length path
each edge of which is crossed by a common edge; if they are endpoints of a path of length
two whose edges cross all edges of an odd length cycle. This list is likely not exhaustive.
In abstract graph homomorphism theory, a graph is not homomorphic to a graph on
fewer vertices if and only if it is a complete graph. In geometric homomorphism theory,
there are many graphs other than complete graphs that are not homomorphic to any geo-
metric graph on fewer vertices. For example, since vertices involved in a common crossing
cannot be identified by geometric homomorphism, there is no geometric homomorphism
of the non-plane realization of C4 into a geometric graph on fewer than four vertices.
In abstract graph homomorphism theory, every graph on n vertices is homomorphic
to Kn. However, not all geometric graphs on n vertices are homomorphic to a given re-
alization of Kn. In fact, two different geometric realizations of Kn are not necessarily
homomorphic to each other. For example, consider the three geometric realizations of K6
given in Figure 1. Note that G2 has a vertex with all incident edges crossed, while G3 does
not; this can be used to prove that there is no geometric homomorphism from G2 to G3.
Also, G3 has more crossings than G2; this can be used to prove that there is no geometric
homomorphism from G3 to G2. On the other hand we can easily argue that while there is
no geometric homomorphism from G2 to G1, the map f : G1 → G2 implied by the given
vertex numbering schemes is a geometric homomorphism.
Since homomorphisms are reflexive and transitive, it is natural to want to use them to
induce a partial order. That is, we would like to define G  H when G → H . However,
graph homomorphisms are not necessarily antisymmetric. It is easy to find geometric (or
abstract) graphs G and H so that G → H and H → G but G and H are not isomorphic.
For example, let H be any geometric graph with a non-isolated vertex z. Add a vertex x
D. L. Boutin et al.: Posets of geometric graphs 271
1
6
45
2
3
1
2
3
45
6
1
2
3
4
5
6
G1 G2 G3
Figure 1: Three geometric realizations of K6
and edge e between x and z, positioned so that e crosses no other edge of H . Call this
new graph G. Identifying x with any neighbor of z gives us G → H . The fact that H is
a subgraph of G gives us H → G. But clearly G and H are not isomorphic. Thus graph
homomorphisms (whether abstract or geometric) do not induce a partial order since they
are not antisymmetric.
In [9], Hell and Nešetřil solve this problem for abstract graphs by using homomor-
phisms to define a partial order on the class of non-isomorphic cores of graphs. The core
of an (abstract or geometric) graph is the smallest subgraph to which it is homomorphic.
In the example discussed above, G and H have isomorphic cores. In this paper we solve
the problem by using geometric homomorphisms to define a partial order on the set of ge-
ometric realizations of a given abstract graph. That is to say, we let G  H if there is
a geometric homomorphism f : G → H that induces an isomorphism on the underlying
abstract graphs. This definition ensures that  is antisymmetric.
The paper is organized as follows. In Section 2 we give formal definitions and develop
tools that help determine whether two geometric realizations are homomorphic. In Section
3 we determine the isomorphism classes and resulting poset, Pn, of realizations of the path
Pn with 2 ≤ n ≤ 6. Additionally we provide the following results: Pn has a unique
minimal and a unique maximal element; if k ≤ n, then Pk is a subposet of Pn; for each
positive integer c less than or equal to the maximum number of crossings, there is at least
one realization of Pn with precisely c crossings. In Section 4 we determine the isomor-
phism classes and resulting poset, Cn, of realizations of the cycle Cn with 3 ≤ n ≤ 6. We
also show that Cn has a unique minimal element and a unique maximal element. Further
if k ≤ n, then Ck is a subposet of Cn. In Section 5 we determine the isomorphism classes
and resulting poset, Kn, of realizations of the complete graph Kn with 3 ≤ n ≤ 6, and we
prove that for all n, Kn contains a chain of length n − 2. In Section 6 we provide some
open questions.
2 Basics, tools, examples
A geometric graph G is a simple graph G =
(
V (G), E(G)
)
together with a straight-line
drawing of G in the plane with vertices in general position (no three vertices are collinear
and no three edges cross at a single point). A geometric graph G with underlying abstract
graph G is called a geometric realization of G; the term rectilinear drawing is also used in
the literature. Two geometric realizations of a graph are considered the same if they have
the same vertex adjacencies and edge crossings. This is formalized below by extending the
272 Ars Math. Contemp. 5 (2012) 269–288
definition of graph isomorphism in a natural way to geometric graphs.
Definition. [1] A geometric isomorphism, denoted f : G→ H , is a bijection f : V (G)→
V (H) such that for all u, v, x, y ∈ V (G),
1. uv ∈ E(G) if and only if f(u)f(v) ∈ E(H), and
2. xy crosses uv in G if and only if f(x)f(y) crosses f(u)f(v) in H .
If there exists a geometric isomorphism f : G → H , we write G ∼= H . Geometric
isomorphism clearly defines an equivalence relation on the set of geometric realizations of
a simple graph G.
Note that in [7, 8] Harborth, et al., give a definition for isomorphism of geometric
graphs that is stricter than the one given here. They require that a geometric isomorphism
also preserve regions and parts of edges. Figure 2 shows two geometric realizations of C6
that have the same crossings (and so are isomorphic by our definition) but have different
regions (and so are not isomorphic in the sense of Harborth). Harborth’s definition is more
geometric; it allows only perturbations of vertex positions within their assigned regions.
The definition used here is more combinatorial; it is a natural generalization of the defini-
tion of graph isomorphism and generalizes easily to geometric graph homomorphism. It
captures facts that come from the geometry, without capturing the geometry itself. This
more combinatorial definition has been used in other works about geometric graph auto-
morphisms and geometric graph homomorphisms. See for instance [1], [2], [3], and [5].
1 2
3
4
5
6
1 2
3
4
5
6
Figure 2: Realizations with the same crossings but different regions
One consequence of the differences in these definitions is that for a given abstract graph
there are (potentially) fewer isomorphism classes of realizations under our definition than
under that of Harborth. Thus if we have an isomorphism class of Harborth et al., and no
pair of representatives is isomorphic by this definition, then we have found all isomorphism
classes under this definition. This is done in Section 5 for all isomorphism classes of
geometric realizations of K3,K4,K5,K6.
Just as the definition of graph isomorphism is extended to geometric graphs, so is the
definition of graph homomorphism.
Definition. [3] A geometric homomorphism, denoted f : G → H , is a function f :
V (G)→ V (H) such that for all u, v, x, y ∈ V (G),
1. if uv ∈ E(G), then f(u)f(v) ∈ E(H), and
2. if xy crosses uv in G, then f(x)f(y) crosses f(u)f(v) in H .
If there is a geometric homomorphism f : G → H , we write G f→ H or simply
G→ H , and we say that G is (geometrically) homomorphic to H .
D. L. Boutin et al.: Posets of geometric graphs 273
Definition. Let G and Ĝ be geometric realizations of a graph G. Set G  Ĝ (or G
f
 Ĝ) if
there exists a (vertex) injective geometric homomorphism f : G→ Ĝ.
Note that since the abstract graphs underlying G and Ĝ are the same, the fact that f is
injective and preserves adjacency means that f induces an isomorphism from G to itself.
It is not difficult to see that this relation is reflexive, transitive, antisymmetric, and hence a
partial order.
Definition. The geometric homomorphism poset of a graph is the set of geometric isomor-
phism classes of its realizations partially ordered by the relation .
2.1 The edge crossing and line/crossing graphs
Recall that the line graph of an abstract graphG, denoted L(G), is the abstract graph whose
vertices correspond to edges of G, with adjacency when the corresponding edges of G are
adjacent. In this section, we define the edge crossing graph, which is similar to the line
graph except that it encodes edge crossings rather than edge adjacencies. In [10] Nešetřil,
et al., proved a correspondence between graph homomorphisms and homomorphisms of
their line graphs. We generalize this to geometric graphs and the union of their line and
crossing graphs.
Definition. Let G be a geometric graph. Define the edge crossing graph, denoted EX(G),
to be the abstract graph whose vertices correspond to edges of G, with adjacency when the
corresponding edges of G cross. Define the line/crossing graph, denoted LEX(G), to be
the 2-edge-colored abstract graph whose vertices correspond to the edges of G, with red
edges in LEX(G) corresponding to adjacent edge pairs inG and black (and dashed) edges
in LEX(G) corresponding to crossing edge pairs in G.
In other words, the line/crossing graph of G is the union of the line graph of G and the
edge crossing graph ofG, with an added edge coloring to keep the meanings of these edges
clear. Figure 3 shows a geometric realization of P6 and its line/crossing graph.
The following theorem is well-known and important to our proofs.
Theorem 2.1. [11] If G has more than four vertices, then G ∼= H ⇐⇒ L(G) ∼= L(H).
Proposition 2.2. Let G and H be geometric graphs on more than four vertices. Then
G  H if and only if there exists a color-preserving graph homomorphism f̃ : LEX(G)→
LEX(H) that restricts to an isomorphism from L(G) to L(H).
Note that using Proposition 2.2 requires that G and H have isomorphic underlying
abstract graphs. Thus we may assume that G and H are geometric realizations of the same
graph.
An alternate way to phrase Proposition 2.2 is to say that if G and Ĝ are geometric real-
izations of the abstract graph G, then G  Ĝ if and only if there exists an isomorphism of
the line graphs that induces a homomorphism of the edge crossing graphs. Thus if there is
no injective homomorphism f̃ : EX(G)→ EX(Ĝ), then G 6 Ĝ. Thus given G and Ĝ, if
EX(G) is not isomorphic to a subgraph of EX(Ĝ), then there is no geometric homomor-
phism G→ Ĝ. However, Proposition 2.2 tells us something stronger. The proposition tells
us that G → Ĝ if and only if there is f̃ ∈ Aut(L(G)) so that f̃(EX(G)) is a subgraph of
EX(Ĝ). For graphs whose line graphs have small automorphism groups, this reduces the
work significantly.
274 Ars Math. Contemp. 5 (2012) 269–288
Example. In Figure 3 we see a realizationP 6 ofP6. Note thatL(P6) ∼= P5 andEX(P 6) ∼=
P2. Each non-plane geometric realization of P6 has edge crossing graph with at least one
edge, so theoretically there are many possible realizations P̂6 to which P 6 might be geo-
metrically homomorphic. However, by Proposition 2.2 a vertex injective homomorphism
f : P 6 → P̂6, taking EX(P 6) to a subgraph of EX(P̂6), needs to be an automorphism of
L(P6). Recall that P 6 as given in Figure 3 has a single crossing that occurs between edges
e1 (with endpoints 1 and 2) and e3 (with endpoints 3 and 4). Applying the two automor-
phisms of L(P6) to this realization, we see that P 6 → P̂6 if and only if P̂6 has one of the
crossings e1 × e3 or e3 × e5. This restricts our search significantly.
1
2
3
4
5
6
e1
e2
e3 e4
e5
Figure 3: P 6 and its line/crossing graph
2.2 Parameters
We next define parameters that help determine whether there is a geometric homomor-
phism between two geometric realizations of the same graph. Proposition 2.3 lists several
properties that follow easily from the definition of these parameters.
K6 K̂6
Figure 4: Vertex labels giving a geometric homomorphism from K6 to K̂6
Figure 4 shows two geometric realizations, K6 and K̂6, of K6. The vertex labeling
gives a geometric homomorphism from K6 to K̂6. Below we define several parameters
for geometric embeddings, which we then use to demonstrate that there is no geometric
homomorphism from K̂6 to K6. In what follows we let ei,j denote the edge from vertex i
to vertex j.
Definition. If G is a geometric realization of a graph G, let cr(G) denote the total number
of crossings in G. For e ∈ E(G) let cr(e) be the number of edges that cross the edge e in
D. L. Boutin et al.: Posets of geometric graphs 275
G. Let E0 (resp., E×) denote the set of edges in G that have cr(e) = 0 (resp., cr(e) > 0).
If |E×| = 0 we say that G is a plane realization of G. Let G0 (resp., G×) denote the
abstract graph on the full vertex set of G whose edge set is E0 (resp., E×). A clique in G
is called a convex clique if its vertices are in convex position. The convex clique number of
G is the maximum size of a convex clique in G, denoted by ω̂(G).
Proposition 2.3. LetG and Ĝ be geometric realizations of a graphG, and supposeG
f
 Ĝ.
Then
1. cr(G) ≤ cr(Ĝ).
2. For each e ∈ E(G), cr(e) ≤ cr(f(e)).
3. |E0(G)| ≥ |E0(Ĝ)| and |E×(G)| ≤ |E×(Ĝ)|.
4. Ĝ0 is a subgraph of G0.
5. ω̂(G) ≤ ω̂(Ĝ).
Example. In the graphs in Figure 4, cr(K6) = 8, cr(K̂6) = 11, |E0(K6)| = 7,
|E0(K̂6)| = 6, ω̂(K6) = 4 and ω̂(K̂6) = 5. Thus parts 1, 3, and 5 of Proposition 2.3
each imply that there is no geometric homomorphism from K̂6 to K6.
Definition. Let G be a geometric realization of a graph G. For each v ∈ V (G), let d0(v)
be the number of uncrossed edges incident to v and let m(v) be the maximum number of
times an edge that is incident to v is crossed.
Proposition 2.4. LetG and Ĝ be geometric realizations of a graphG, and supposeG
f
 Ĝ.
Then for each v ∈ V (G), d0(v) ≥ d0(f(v)) and m(v) ≤ m(f(v)).
Example. In the example in Figure 4, consider the vertex v = 1 in K6 and its image f(v)
in K̂6. Then d0(v) = 2 and m(v) = 2, while d0(f(v)) = 2 and m(f(v)) = 3.
An effective way to use Proposition 2.4 is to compare the values of each parameter over
all vertices at once. This motivates the following definitions.
Definition. For a geometric graph G, let D0(G) (resp., M(G)) be the vector whose coor-
dinates contain the values {d0(v)}v∈V (G) (resp., {m(v)}v∈V (G)), listed in non-increasing
order.
Definition. Given two vectors ~x and ~y in Zn, we say that ~x ≤ ~y if each coordinate of ~x has
value that is at most the value in the corresponding coordinate of ~y. Let X,Y be the vector
of values of ~x and ~y listed in non-increasing order.
Lemma 2.5. Let ~x, ~y ∈ Zn. If ~x ≤ ~y, then X ≤ Y .
Proof. By definition, the first coordinate of X is X1 = max
{
xi | 1 ≤ i ≤ n
}
, and so
X1 = xi1 for some i1 ∈ {1, . . . , n}. But by assumption, X1 = xi1 ≤ yi1 ≤ max
{
yi | 1 ≤
i ≤ n
}
= Y1.
More generally, for all 2 ≤ k ≤ n, the k-th entry of X is less than or equal to at least
k entries of ~x, say xi1 , . . . , xik . Further by assumption, for each h, xih ≤ yih . Since there
are (at least) k coordinates of ~y that have value at least Xk, the value Yk must be at least
that large. Thus the k-th entry of X is less than or equal to at least k coordinates of ~Y , and
so Xk ≤ Yk. Thus X ≤ Y .
276 Ars Math. Contemp. 5 (2012) 269–288
Corollary 2.6. Let G and Ĝ be geometric realizations of a graph G, and suppose G
f
 Ĝ.
Then
1. D0(G) ≥ D0(Ĝ);
2. M(G) ≤M(Ĝ).
In Figure 4,D0(K6) = (3, 3, 3, 2, 2, 1) ≥ D0(K̂6) = (3, 2, 2, 2, 2, 1), whileM(K6) =
(4, 4, 3, 3, 2, 2) ≤M(K̂6) = (4, 4, 3, 3, 3, 2).
3 Posets for geometric paths
We now determine Pn, the geometric homomorphism poset of the path Pn on n vertices,
for n = 2, . . . , 6, and we state some properties of this poset for general n. Throughout
this section, we denote the vertices of Pn by 1, 2, . . . , n, and its edges by ei = {i, i +
1}, i = 1, . . . , n− 1. The following two lemmas are helpful in determining the geometric
realizations of Pn.
Lemma 3.1. If a geometric graph G contains P5 as a subgraph, with vertices and edges
numbered as above and e1 × e3 and e2 × e4 are both crossings in G, then so is e1 × e4.
Proof. SupposeG has both of the crossings e1×e3 and e2×e4. Let ` be the line determined
by edge e1. Since e1 crosses e3, we may assume that vertex 3 lies above ` and vertex 4
lies below `, as indicated in Figure 5. Let C be the cone with vertex 4 and sides extending
through vertices 1 and 2 (indicated by dashed lines in Figure 5). For e3 to cross e1, both 3
and e2 must be inside C. For e4 to cross e2, both 5 and e4 must lie in the cone with vertex
4 and sides through 2 and 3, and 5 must also lie above e2. This forces e4 to cross e1 in
addition to crossing e2.
1 2
3
4
Figure 5: For use in the proof of Lemma 3.1
Lemma 3.2. A geometric realization of Pn has at most (n− 2)(n− 3)/2 edge crossings.
Moreover, this bound is tight.
Proof. The only possible crossing edge pairs in any geometric realization of Pn are of
the form ei × ej with j − i ≥ 2; thus for any i = 1, . . . , n − 3, there are n − i − 2
higher-numbered edges that can cross ei. A straightforward algebraic calculation shows
that (n− 2)(n− 3)/2 is an upper bound on the number of edge crossings. Figure 6 gives
a geometric realization of P7 that achieves this bound.
To determine up to isomorphism all the possible geometric realizations of Pn, for n =
2, . . . , 5, first list all sets whose elements are pairs of edges ei × ej with j − i ≥ 2. Next
D. L. Boutin et al.: Posets of geometric graphs 277
Figure 6: P 7 with the maximum number of crossings
eliminate any sets that violate Lemma 3.1, and identify any sets that are equivalent under
an automorphism of Pn. Recall that the only automorphisms of Pn are the identity and the
map that reverses the order of the vertices. Finally, check that each of the remaining sets
corresponds to a geometric realization.
To determine the structure of the geometric homomorphism poset, recall that by Propo-
sition 2.2, Pn  P̂n if and only if there is f̃ ∈ Aut(L(Pn)) that induces a graph ho-
momorphism from EX(Pn) to EX(P̂n). The graph L(Pn) = Pn−1 has only the two
automorphisms mentioned above. Thus for each ordered pair of realizations, we need only
check two automorphisms to see if they extend to color-preserving homomorphisms of the
corresponding line/crossing graph.
For n = 2, . . . , 5, all sets that satisfy Lemma 3.1 have geometric realizations. We state
the poset results for P2, . . . , P5 below.
Theorem 3.3. Let Pn be the poset of geometric realizations of Pn.
1. Each of P2 and P3 is trivial, containing only the plane realization.
2. P4 is a chain of two elements, in which the plane realization is the unique minimal
element, and the realization with crossing e1 × e3 is the unique maximal element.
3. P5 has the following five non-isomorphic geometric realizations and Hasse diagram
as given in Figure 7: 0.1 = ∅ (the plane realization) ; two 1-crossing realizations,
1.1 = {e1 × e3} ≡ {e2 × e4} and 1.2 = {e1 × e4}; a single 2-crossing realization,
2.1 = {e1 × e3, e1 × e4} ≡ {e1 × e4, e2 × e4}; and a single 3-crossing realization,
3.1 = {e1 × e3, e1 × e4, e2 × e4}.
Proof. It is straightforward to find geometric realizations with the given sets of crossings.
These realizations, together with their line/crossing graphs (which aid in determining the
poset relations), appear in [4]. It follows from Lemmas 3.1 and 3.2 that there are no other
realizations.
For P6, there is one set of crossing edge pairs that satisfies Lemma 3.1, but which does
not correspond to a geometric realization of P6, namely {e1 × e3, e1 × e4, e1 × e5, e2 ×
e5, e3 × e5}. The following lemma shows that this set can also be eliminated.
Lemma 3.4. Suppose a geometric graph G contains P6 as a subgraph, with vertices and
edges numbered in the standard way. If e1 × e3, e1 × e4, e1 × e5, e2 × e5, and e3 × e5 are
crossings in G, then so is e2 × e4.
278 Ars Math. Contemp. 5 (2012) 269–288
0.1
1.1 1.2
2.1
3.1
Figure 7: The Hasse diagram for P5
Proof. Since edges e1 and e3 cross, we may assume without loss of generality that e2 is
horizontal, and that e1 and e3 lie above e2, as indicated in Figure 8. Since G contains the
crossing e1 × e4, vertex 5 is in one of the regions T,E, or S shown in Figure 8. If vertex 5
is in E or T , then e5 cannot cross all three of the edges e1, e2, and e3. Thus vertex 5 is in
S, forcing the crossing e2 × e4.
1
2 3
4
T
S
E
Figure 8: For use in the proof of Lemma 3.4
We are now able to list all the non-isomorphic geometric realizations of P6 and give the
Hasse diagram for P6.
Theorem 3.5. The poset P6 has the following thirty-one non-isomorphic geometric real-
izations and has Hasse diagram as given in Figure 9.
0 crossings: 0.1 = ∅;
1 crossing: 1.1 = {e1×e3} ≡ {e3×e5}, 1.2 = {e1×e4} ≡ {e2×e5}, 1.3 = {e1×e5},
1.4 = {e2 × e4};
2 crossings: 2.1 = {e1×e3, e1×e4}, 2.2 = {e1×e3, e1×e5}, 2.3 = {e1×e3, e2×e5}, 2.4
= {e1×e3, e3×e5}, 2.5 = {e1×e4, e1×e5}, 2.6 = {e1×e4, e2×e4}, 2.7 = {e1×e4, e2×e5},
2.8 = {e1 × e5, e2 × e4};
3 crossings: 3.1 = {e1 × e3, e1 × e4, e1 × e5}, 3.2 = {e1 × e3, e1 × e4, e2 × e4}, 3.3 =
{e1×e3, e1×e4, e2×e5}, 3.4 = {e1×e3, e1×e4, e3×e5}, 3.5 = {e1×e3, e1×e5, e2×e5}, 3.6
= {e1×e3, e1×e5, e3×e5}, 3.7 = {e1×e4, e1×e5, e2×e4} 3.8 = {e1×e4, e1×e5, e2×e5},
3.9 = {e1 × e4, e2 × e4, e2 × e5};
4 crossings: 4.1 = {e1×e3, e1×e4, e1×e5, e2×e4} ≡ {e1×e5, e2×e4, e2×e5, e3×
e5}, 4.2 = {e1 × e3, e1 × e4, e1 × e5, e2 × e5} ≡ {e1 × e4, e1 × e5, e2 × e5, e3 × e5},
4.3 = {e1 × e3, e1 × e4, e1 × e5, e3 × e5} ≡ {e1 × e3, e1 × e5, e2 × e5, e3 × e5}, 4.4
D. L. Boutin et al.: Posets of geometric graphs 279
= {e1 × e3, e1 × e4, e2 × e4, e2 × e5} ≡ {e1 × e4, e2 × e4, e2 × e5, e3 × e5}, 4.5 =
{e1 × e3, e1 × e4, e2 × e5, e3 × e5}, 4.6 = {e1 × e4, e1 × e5, e2 × e4, e2 × e5};
5 crossings: 5.1 = {e1×e3, e1×e4, e1×e5, e2×e4, e2×e5} ≡ {e1×e4, e1×e5, e2×
e4, e2 × e5, e3 × e5}, 5.2 = {e1 × e3, e1 × e4, e2 × e4, e2 × e5, e3 × e5};
6 crossings: 6.1 = {e1 × e3, e1 × e4, e1 × e5, e2 × e4, e2 × e5, e3 × e5}.
Proof. It is straightforward to find geometric realizations with the given sets of crossings.
These realizations, together with their line/crossing graphs (which aid in determining the
poset relations), appear in [4]. It follows from Lemmas 3.1, 3.2, and 3.4 that there are no
others.
The following theorem lists some properties of Pn for n ≥ 3.
Theorem 3.6. For n ≥ 3, Pn has the following properties.
1. There is a unique minimal element, corresponding to the plane realization of Pn.
2. There is a unique maximal element, corresponding to the realization of Pn with
(n− 2)(n− 3)/2 crossings.
3. Pn has a chain of size (n− 2)(n− 3)/2 + 1. In particular, for each c with 0 ≤ c ≤
(n− 2)(n− 3)/2, there is at least one realization of Pn with exactly c crossings.
4. For 1 ≤ k ≤ n, Pk is isomorphic to a sub-poset of Pn.
Proof. Properties 1 and 2 are easily seen to be true. For Property 3, consider a geometric
realization Pn of Pn with c ≥ 1 crossings. Such a realization can be modified to create a
new realization P̂n with c− 1 crossings, and with P̂n ≺ Pn, by sliding the vertex n along
edge en−1 until it passes over a crossing edge, and then erasing the section of en−1 that
extends beyond this point. If en−1 has no crossings, we slide vertices n and n − 1 along
edge en−2, erasing what remains of en−1 and en−2, and so on. We can continue in a similar
manner to remove one crossing at a time until there are none left; the process is illustrated
in Figure 10. Since Lemma 3.2 guarantees that Pn has a realization with (n− 2)(n− 3)/2
crossings, Property 3 follows.
For Property 4, suppose we have some geometric realization of Pk. We can replace the
uncrossed segment of edge ek−1 nearest to vertex k with a path from k to n to obtain a
geometric realization of Pn with the same crossings. By doing this for each realization of
Pk, we see that its poset of geometric realizations is isomorphic to a sub-poset of the poset
of geometric realizations of Pn.
A cover of an element x in a poset P is an element y ∈ P such that x ≺ y and no z ∈ P
satisfies x ≺ z ≺ y. P is called a graded poset if there is a rank function ρ : P → N such
that for all x, y ∈ P , 1) all minimal elements have the same value under the rank function,
2) if x ≺ y, then ρ(x) < ρ(y), and 3) if y covers x, then ρ(y) = ρ(x) + 1. Note that if
a poset is graded then all maximal chains between a given pair of elements must have the
same length.
A reasonable conjecture for geometric homomorphism posets is that the number of
edge crossings acts as a rank function. Condition 1 holds by Proposition 2.3. However,
Condition 2 fails to hold in exactly one instance in P6: realization 6.1 covers realization
4.3, yet it has two more crossings. In fact, the poset P6 does not admit any rank function,
because it has maximal chains between 0.1 and 6.1 which have different lengths: 0.1 ≺
1.4 ≺ 2.8 ≺ 3.7 ≺ 4.6 ≺ 5.1 ≺ 6.1 and 0.1 ≺ 1.1 ≺ 2.2 ≺ 3.5 ≺ 4.3 ≺ 6.1. Hence,
280 Ars Math. Contemp. 5 (2012) 269–288
P6 is not a graded poset. It follows from Property 4 that Pn is not a graded poset for any
n ≥ 6.
0.1
1.1 1.2 1.3 1.4
2.1 2.22.32.4 2.5 2.62.7 2.8
3.1 3.23.33.4 3.53.6 3.73.8 3.9
4.14.24.3 4.44.5 4.6
5.1
6.1
5.2
Figure 9: The Hasse diagram for P6
A lattice is a poset in which any two elements have a unique supremum (join) and
unique infimum (meet). Figure 9 shows that P6 is not a lattice because (for example)
realizations 3.5 and 3.1 have both 4.3 and 4.2 as suprema, and realizations 4.3 and 4.2 have
both 3.5 and 3.1 as infima. It follows from Property 4 that Pn is not a lattice for any n ≥ 6.
1 2
3
4
5
6
7
1 2
3
4
5
6
7
1 2
3
4
5
6
7
Figure 10: Geometric realizations of P7 with 10 crossings, 6 crossings, and 3 crossings
4 Posets for geometric cycles
We now determine Cn, the geometric homomorphism poset of the cycle Cn on n vertices,
for n = 3, . . . , 6, and we state some properties of this poset for general n. Throughout this
section we denote the vertices of Cn by 1, 2, . . . , n, and its edges by ei = {i, i + 1}, i =
1, . . . , n− 1, and en = {n, 1}.
The maximum number of crossings in a geometric realization of Cn was determined in
1977 by Furry and Kleitman [6]; their results are summarized in the next lemma.
D. L. Boutin et al.: Posets of geometric graphs 281
Lemma 4.1. [6] For n ≥ 3, a geometric realization of Cn has at most n(n− 3)/2 edge
crossings if n is odd and n(n− 4)/2 + 1 edge crossings if n is even. Moreover, these
bounds are tight.
Figure 11 shows such a realization for n = 10.
1
2
3
4
5
6
7
8
9
10
Figure 11: A realization of C10 with the maximum number of crossings
The techniques of the previous section can be used to find the elements of Cn. For
3 ≤ n ≤ 5, every set of crossing edge pairs that satisfies Lemma 3.1 corresponds to a
geometric realization. For C6, this is the case for all geometric realizations with at most
two crossings. For realizations with three or more crossings, some cases require additional
lemmas.
Lemma 4.2. Suppose Cn is a geometric realization of the cycle Cn that has crossings
ei × ek and ej × e`, where i < j < k < `. Then there is at least one additional crossing
eα × eβ where i ≤ α ≤ k and k ≤ β ≤ i (mod n) (and {α, β} 6= {i, k}).
Proof. Suppose there is no such additional crossing. Place a vertex v at the crossing ei×ek,
subdividing each of those two edges. Starting at edge {v, i + 1} of the modified graph,
follow the cycle in order of increasing vertex number, coloring each edge red, until the
crossing ei×ek is reached again at edge {k, v}. Then follow the rest of the cycle, beginning
at edge {v, k+1}, coloring each edge blue, until the final edge {i, v} is reached. Note that
edge ej is red and edge e` is blue. The red cycle is a closed, but not necessarily simple,
rectilinear curve in the plane. From the hypotheses of the lemma and our assumption that
the conclusion is false, this red curve does not cross either of the edges {i, v} and {v, k+1},
so these two edges lie in the same region of the plane determined by the red curve. If we
now follow the blue curve starting at k+1, then the red-blue crossing ej×e` takes the blue
curve into a different region of the plane determined by the red curve. But since we have
assumed that the additional crossing of the lemma does not exist, the blue curve cannot
return to end at vertex i, which is a contradiction.
Lemma 4.3 is a multi-part technical lemma. We prove the first part below; the proofs
of the others, which are similar to the proof of Lemma 3.4, appear in [4].
Lemma 4.3. Let C6 be a geometric realization of the cycle C6, with edges labeled con-
secutively, e1, e2, . . . , e6.
1. If C6 contains the crossings e1× e3, e1× e4, and e1× e5, then it doesn’t contain the
crossing e2 × e6.
282 Ars Math. Contemp. 5 (2012) 269–288
2. If C6 contains the crossings e1 × e3, e1 × e4, e1 × e5, e2 × e4, and e4 × e6, then it
also contains the crossing e2 × e5.
3. IfC6 contains the crossings e1×e3, e1×e4, e2×e4, and e2×e5, then it also contains
at least one of the crossings e1 × e5, e3 × e5, e3 × e6.
4. IfC6 contains the crossings e1×e3, e1×e4, e2×e5, and e4×e6, then it also contains
at least one of the crossings e2 × e4, e3 × e5, e3 × e6.
5. IfC6 contains the crossings e1×e3, e1×e4, e2×e5, and e3×e6, then it also contains
at least one of the crossings e2 × e4, e2 × e6, e3 × e5, e4 × e6.
Proof. For part 1, suppose C6 contains the crossings e1×e3, e1×e4, and e1×e5. Let h be
the line through edge e1. Since e1 crosses every edge of the path joining vertices 3 and 6,
the vertices 3 and 6 lie on opposite sides of h. Thus the edges e2 = {2, 3} and e6 = {6, 1}
also lie on opposite sides of h and so do not cross. The proofs of parts 2-5 are similar and
appear in [4].
Part 1 and its proof generalize to give us the following corollary.
Corollary 4.4. Let Cn be a geometric realization of the cycle Cn, where n ≥ 4 is even.
If Cn contains the crossings e1 × e3, e1 × e4, . . . , e1 × en−1, then it doesn’t contain the
crossing e2 × en.
To determine the the elements of the poset C6, look at all possible sets of crossing edge
pairs, and delete sets that don’t satisfy Lemmas 3.1, 3.4, 4.2 or 4.3.
Next, identify those that are equivalent under an automorphism of Cn. There are 2n
such automorphisms: each of the rotations and each of these composed with the reflection
map. To determine the geometric homomorphisms among the remaining sets, recall that by
Proposition 2.2, it suffices to look for automorphisms of the line graph L(Cn) that extend
to homomorphisms on the edge crossing graphs. Since L(Cn) = Cn, these automorphisms
are precisely the 2n automorphisms mentioned above.
Theorem 4.5 lists the elements of the poset of geometric realizations of Cn for 3 ≤ n ≤
6; all nontrivial realizations are given up to isomorphism.
Theorem 4.5. Let Cn be the poset of geometric realizations of Cn.
1. C3 is trivial, containing only the plane realization.
2. C4 is a chain of two elements, in which the plane realization is the unique minimal
element, and the realization with crossing e1 × e3 is the unique maximal element.
3. C5 is a chain of five elements: the plane realization 0.1 = ∅, 1.1 = {e1 × e3},
2.1 = {e1×e3, e1×e4}, 3.1 = {e1×e3, e1×e4, e2×e4}, and 5.1 = {e1×e3, e1×
e4, e2 × e4, e2 × e5, e3 × e4}.
4. C6 has the following twenty-six non-isomorphic geometric realizations and has Hasse
diagram as given in Figure 12:
0 crossings: 0.1 = ∅ (the plane realization);
1 crossing: 1.1 = {e1 × e3}, 1.2 = {e1 × e4};
2 crossings: 2.1 = {e1×e3, e1×e4}, 2.2 = {e1×e3, e1×e5}, 2.3 = {e1×e3, e4×
e6};
D. L. Boutin et al.: Posets of geometric graphs 283
3 crossings: 3.1 = {e1×e3, e1×e4, e1×e5}, 3.2 = {e1×e3, e1×e4, e2×e4}, 3.3 =
{e1 × e3, e1 × e4, e2 × e5}, 3.4 = {e1 × e3, e1 × e4, e3 × e5}, 3.5 = {e1 × e3, e1 ×
e4, e3×e6}, 3.6 = {e1×e3, e1×e4, e4×e6}, 3.7 = {e1×e3, e1×e5, e3×e5}, 3.8 =
{e1 × e4, e2 × e5, e3 × e6};
4 crossings: 4.1 = {e1× e3, e1× e4, e1× e5, e2× e4}, 4.2 = {e1× e3, e1× e4, e1×
e5, e2×e5}, 4.3 = {e1×e3, e1×e4, e1×e5, e3×e5}, 4.4 = {e1×e3, e1×e4, e2×
e5, e3 × e5}, 4.5 = {e1 × e3, e1 × e4, e3 × e6, e4 × e6};
5 crossings: 5.1 = {e1× e3, e1× e4, e1× e5, e2× e4, e2× e5}, 5.2 = {e1× e3, e1×
e4, e2×e4, e2×e5, e3×e5}, 5.3 = {e1×e3, e1×e4, e2×e4, e2×e5, e3×e6}, 5.4 =
{e1 × e3, e1 × e4, e2 × e5, e3 × e6, e4 × e6};
6 crossings: 6.1 = {e1 × e3, e1 × e4, e1 × e5, e2 × e4, e2 × e5, e3 × e5}, 6.2 =
{e1 × e3, e1 × e4, e1 × e5, e2 × e4, e2 × e5, e3 × e6};
7 crossings: 7.1 = {e1 × e3, e1 × e4, e1 × e5, e2 × e4, e2 × e5, e3 × e6, e4 × e6}.
Proof. It is straightforward to find geometric realizations with the given sets of crossings.
These realizations, together with their line/crossing graphs (which aid in determining the
poset relations) appear in [4]. It follows from Lemmas 3.1, 3.4, 4.1, 4.2 and 4.3 that there
are no other realizations.
0.1
1.11.2
2.1 2.22.3
3.8 3.13.23.3 3.43.5 3.6 3.7
4.14.2 4.3
5.2
5.3 4.4
5.4
4.5
5.1
6.16.2
7.1
Figure 12: The Hasse diagram for C6
Unlike the case of Pn, we see from the geometric realizations of C5 that not every pos-
sible number of crossings up to the maximum is necessarily achieved. On the other hand,
C6 has at least one realization with each number of crossings from 0 up to its maximum of
7. Furry and Kleitman have shown that this is representative of the geometric realizations
of all odd and even cycles. This is stated in Theorem 4.6 below.
284 Ars Math. Contemp. 5 (2012) 269–288
Theorem 4.6. [6] For n even, n ≥ 4, Cn can have any number of crossings from 0 up to
the maximum of n(n− 4)/2 + 1. For n odd, n ≥ 3, Cn can have any number of crossings
from 0 up to the maximum of n(n − 3)/2, except there is no geometric realization with
n(n− 3)/2− 1 crossings.
Finally we mention three more properties that are true in general for any geometric
realization of the cycle Cn. The first two are obvious, and the third is easy to see, since
any realization of Cn can be replaced by one of Cn+1, by subdividing the edge en into two
edges, en and en+1, so that the new edge en+1 has no crossings.
Theorem 4.7. For n ≥ 3, the poset Cn has the following properties.
1. There is a unique minimal element, corresponding to the plane realization of Cn.
2. There is a unique maximal element, corresponding to the geometric realization with
the maximum number of crossings, as given in Theorem 4.6.
3. For 3 ≤ k ≤ n, the poset Ck is isomorphic to a sub-poset of Cn.
Note that C6 is not a graded poset because it has maximal chains between 0.1 and 6.1
which have different lengths: 0.1 ≺ 1.1 ≺ 2.2 ≺ 3.7 ≺ 4.3 ≺ 6.1 and 0.1 ≺ 1.1 ≺ 2.2 ≺
3.1 ≺ 4.1 ≺ 5.1 ≺ 6.1. Thus by Property 2, for all n ≥ 6, Cn is not a graded poset.
Also, C6 is not a lattice because, for example, realizations 2.1 and 2.2 do not have a unique
supremum. By Property 2, Cn is not a lattice for all n ≥ 6.
5 Posets for geometric cliques
We now determine Kn, the geometric homomorphism poset of the clique Kn for n =
3, . . . , 6, and we state some properties of this poset for general n. Throughout this sec-
tion we denote the vertices of Kn by 1, 2, . . . , n, and its edges by eij = {i, j}, i 6= j ∈
{1, . . . , n}.
In [8], Harborth and Thürmann give all non-isomorphic geometric realizations of Kn
for 3 ≤ n ≤ 6. Recall that their definition for geometric isomorphism is stricter than
the definition being used here. However, that only means that in general, our set of non-
isomorphic geometric realizations may be smaller than theirs. That is, two geometric real-
izations that Harborth and Thürmann consider non-isomorphic, we may consider isomor-
phic. However, in the cases K3,K4,K5,K6, all pairs that are non-isomorphic according
to Harborth are also non-isomorphic according to us.
Theorem 5.1. Let Kn be the poset of geometric realizations of Kn.
1. K3 is trivial, containing only the plane realization.
2. K4 is a chain of two elements, in which the plane realization is the unique minimal
element, and the realization with crossing e1,3× e2,4 is the unique maximal element.
3. K5 is a chain of three elements: 1.1 = {e3,5 × e2,4}, 3.1 = {e1,4 × e2,5, e1,4 × e3,5,
e2,4×e3,5, }, and 5.1 = {e1,3×e2,4, e1,3×e2,5, e1,4×e2,5, e1,4×e3,5, e2,4×e3,5}.
4. K6 has Hasse diagram as given in Figure 13 with fifteen non-isomorphic geometric
realizations:
3 crossings: 3.1 = {e1,3 × e2,6, e1,4 × e2,5, e3,5 × e4,6};
4 crossings: 4.1 = {e1,3 × e2,6, e1,4 × e3,5, e1,4 × e5,6, e3,5 × e4,6};
D. L. Boutin et al.: Posets of geometric graphs 285
5 crossings: 5.1 = {e1,3 × e2,4, e1,3 × e2,6, e1,4 × e2,6, e1,4 × e3,6, e2,4 × e3,6},
5.2 = {e1,3 × e2,6, e1,4 × e2,6, e1,4 × e3,5, e1,4 × e3,6, e3,5 × e4,6};
6 crossings: 6.1 = {e1,4×e2,5, e1,4×e2,6, e1,4×e3,6, e2,4×e3,6, e2,5×e3,6, e2,5×
e4,6};
7 crossings: 7.1 = {e1,3×e2,5, e1,3×e2,6, e1,4×e2,5, e1,4×e3,5, e1,4×e5,6, e1,6×
e2,5, e3,5 × e4,6}, 7.2 = {e1,3 × e2,6, e1,4 × e2,5, e1,4 × e3,5, e1,5 × e4,6, e2,4 ×
e3,5, e2,5 × e4,6, e3,5 × e4,6};
8 crossings: 8.1 = {e1,3×e2,4, e1,3×e2,6, e1,4×e3,5, e1,4×e5,6, e1,6×e2,4, e2,4×
e3,5, e2,4 × e5,6, e3,5 × e4,6}, 8.2 = {e1,3 × e2,4, e1,3 × e2,6, e1,4 × e2,6, e1,4 ×
e3,6, e1,5 × e2,6, e1,5 × e3,6, e1,5 × e4,6, e2,4 × e3,6};
9 crossings: 9.1 = {e1,3×e2,5, e1,3×e2,6, e1,4×e2,5, e1,4×e2,6, e1,4×e3,5, e1,4×
e3,6, e2,5 × e3,6, e2,5 × e4,6, e3,5 × e4,6}, 9.2 = {e1,3 × e2,4, e1,3 × e2,5, e1,3 ×
e2,6, e1,4 × e2,5, e1,4 × e2,6, e1,4 × e3,6, e2,4 × e3,6, e2,5 × e3,6, e2,5 × e4,6};
10 crossings: 10.1 = {e1,3×e2,4, e1,3×e2,5, e1,3×e2,6, e1,4×e2,5, e1,4×e3,5, e1,4×
e5,6, e1,6 × e2,5, e2,4 × e3,5, e2,4 × e3,6, e3,5 × e4,6};
11 crossings: 11.1 = {e1,3×e2,4, e1,3×e2,5, e1,3×e2,6, e1,4×e2,5, e1,4×e3,5, e1,4×
e5,6, e1,6 × e2,4, e1,6 × e2,5, e2,4 × e3,5, e2,4 × e5,6, e3,5 × e4,6};
12 crossings: 12.1 = {e1,3×e2,4, e1,3×e2,5, e1,3×e2,6, e1,4×e2,5, e1,4×e2,6, e1,4×
e3,5, e1,4 × e3,6, e2,4 × e3,5, e2,4 × e3,6, e2,5 × e3,6, e2,5 × e4,6, e3,5 × e4,6};
15 crossings: 15.1 = {e1,3×e2,4, e1,3×e2,5, e1,3×e2,6, e1,4×e2,5, e1,4×e2,6, e1,4×
e3,5, e1,4 × e3,6, e1,5 × e2,6, e1,5 × e3,6, e1,5 × e4,6, e2,4 × e3,5, e2,4 × e3,6, e2,5 ×
e3,6, e2,5 × e4,6, e3,5 × e4,6}.
Proof. Since Aut(Kn) contains all possible permutations of the vertices, it does not make
our job easier to first restrict our search for homomorphisms to those that are induced by
automorphisms of the underlying abstract graph. Thus we use the tools of Subsection 2.2
rather than those of Subsection 2.1. Drawings of the realizations of K5 and K6, as well
justifications of the poset relations and non-relations, appear in [4].
3.1
7.1 7.28.19.1
4.1
8.29.2
5.1
10.1
5.26.1
11.1
15.1
12.1
Figure 13: The Hasse diagram for K6
Observe that K6 has five minimal elements and three maximal ones. As with cycles,
not every possible number of crossings, from 3 up to the maximum of 15, is achieved; there
are no realizations of K6 containing 13 crossings or 14 crossings. Clearly, the number of
286 Ars Math. Contemp. 5 (2012) 269–288
edge crossings cannot act as a rank function. In fact, K6 is not a graded poset because
it has maximal chains between 3.1 and 15.1 of different lengths: 3.1 ≺ 7.2 ≺ 15.1 and
3.1 ≺ 9.1 ≺ 12.1 ≺ 15.1. Moreover, K6 is not a lattice, because realizations 3.1 and 4.1
do not have a unique supremum.
Although K6 has no rank function, the function taking a realization to the number of
vertices in the boundary of its convex hull is order-preserving. In Figure 13, all realizations
displayed on the bottom level of the Hasse diagram have 3 vertices in the boundary of the
convex hull, those on the second level have 4, those on the third level have 5 and realization
15.1 has 6.
Theorem 5.2. For all n ≥ 3,Kn contains a maximal chain of length n−2. More precisely,
Kn contains a chain of the form
H3 ≺ H4 ≺ · · · ≺ Hn
where Hk denotes a geometric realization of Kn with k vertices on the boundary of its
convex hull.
Proof. We start with a template; consider the circle x2 + (y + 1)2 = 4 in the xy plane,
together with the two tangent lines at (−
√
3, 0) and (
√
3, 0) that intersect at (0, 3). Place
n − 1 vertices along the upper portion of the circle, starting at (−
√
3, 0) and ending at
(
√
3, 0); they should be roughly evenly spaced, but in general position. Label the leftmost
one n, and the remaining ones 2, 3, . . . , n − 1 from left to right. Add another vertex at
(0, 3) and label it 1. To complete the template, for each k ∈ {2, 3, . . . , n − 2}, add a ray
from vertex 1 through vertex k and mark where it intersects the lower portion of the circle
with (n− k + 1)∗. See Figure 14.
Joining all pairs of vertices in the template with an edge gives us H3. Note that the
boundary of its convex hull consists of vertices 1, n and n − 1 and that all crossings
in H3 occur in the geometric subgraph induced by the vertices 2, 3, . . . , n. To get H4,
slide vertex n − 1 clockwise along the circle to position (n − 1)∗. Then slide vertices
2 through n − 2 clockwise ‘one spot’ along the upper portion of the circle. This is now
a geometric realization of Kn in which the boundary of the convex hull consists of the
four vertices 1, n − 2, n − 1 and n. Since vertices 2, 3, . . . , n are still in convex posi-
tion, no crossings of H3 have been lost. However the edge {1, n − 1} now crosses edges
{2, n}, {3, n}, . . . , {n− 2, n}. Thus H3 ≺ H4. To get H5, move vertex n− 2 to position
(n − 2)∗ and shift vertices 2 through n − 3 clockwise another ‘one spot’ along the circle.
This gives a geometric realization in which the boundary of the convex hull consists of the
vertices 1, n − 3, n − 2, n − 1 and n. Again, no edge crossings have been lost, but edge
{1, n − 2} now crosses {2, n}, {3, n}, . . . , {n − 3, n}. Iterating this process yields the
chain described in the theorem.
To prove the maximality of this chain, note that its final element Hn has all n vertices
in convex position and so has the maximum number of crossings of any realization of Kn
and therefore has no successor in Kn. Next, suppose that f : H → H3 is an injective
geometric homomorphism. By Proposition 2.4, all edges incident to vertex v = f−1(1)
must be uncrossed. Let w, x, y, z be any other four vertices in H; if they are not in convex
position, then one of them, say w, must lie in the interior of the convex hull of the other
three. This would imply that the edge {v, w} is crossed in H , a contradiction. Hence all
n− 1 other vertices in H lie in convex position, implying that in fact H ∼= H3.
D. L. Boutin et al.: Posets of geometric graphs 287
1
n
2
3
n-1
n-2
n-3
n-1
*
n-2
*
3
*
4
*
Figure 14: Template for the proof of Theorem 5.2
Each of the posets K4 and K5 is precisely the chain given in Theorem 5.2. Within K6,
the chain constructed in Theorem 5.2 is 5.1 ≺ 9.2 ≺ 12.1 ≺ 15.1.
6 Open questions
1. Are there (closed or recursive) formulas for the number of elements in Pn or Cn?
2. For 3 ≤ k ≤ n, is Kk a sub-poset of Kn?
3. If Kn ≺ K̂n, must the number of vertices in the convex hull of Kn be strictly less
than that of K̂n? If so, then the chain constructed in Theorem 5.2 is a maximum
chain.
4. We saw that K6 has a maximal chain of length 2. What is the length of a smallest
possible maximal chain in Kn?
5. What is the geometric homomorphism poset for other common families of graphs? In
[5], Cockburn and Song have determined the geometric homomorphism poset K2,n
for one family of complete bipartite graphs.
288 Ars Math. Contemp. 5 (2012) 269–288
References
[1] M. O. Albertson and D. L. Boutin, Distinguishing geometric graphs, J. Graph Theory 53
(2006), 135–150.
[2] M. O. Albertson and D. L. Boutin, Automorphisms and distinguishing numbers of geometric
cliques, Discrete Comput. Geom. 39 (2008), 778–785.
[3] D. Boutin and S. Cockburn, Geometric graph homomorphisms, J. Graph Theory 69 (2012),
97–113.
[4] D. Boutin, S. Cockburn, A. Dean, and A. Margea, Posets of geometric graphs, with appendices,
arXiv.org, 2011.
[5] S. Cockburn and Y. Song, The homomorphism poset of K2,n, arXiv.org, 2012.
[6] W. Furry and D. Kleitman, Maximal rectilinear crossing of cycles, Studies in Appl. Math., 56
(1977), 159–167.
[7] H. Harborth, Drawings of the cycle graph, Congr. Numer. 66 (1988), 15–22, Nineteenth
Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA,
1988).
[8] H. Harborth and Ch. Thürmann, Numbers of edges without crossings in rectilinear drawings
of the complete graph, Congr. Numer. 119 (1996), 79–83.
[9] P. Hell and J. Nešetřil, Graphs and homomorphisms, volume 28 of Oxford Lecture Series in
Mathematics and its Applications, Oxford University Press, Oxford, 2004.
[10] J. Nešetřil, Homomorphisms of derivative graphs, Discrete Math. 1 (1971/72), 257–268.
[11] H. Whitney, Congruent Graphs and the Connectivity of Graphs, Amer. J. Math., 54 (1932),
150–168.