Distinguishing geometric graphs

We begin the study of distinguishing geometric graphs. Let (G) over bar be a geometric graph. An automorphism of the underlying graph that preserves both crossings and noncrossings is called a geometric automorphism. A labeling, f : V((G) over bar -> {1, 2,..., r}, is said to be r-distinguishing if no nontrivial geometric automorphism preserves the labels. The distinguishing number of (G) over bar is the minimum r such that (G) over bar has an r-distinguishing labeling. We show that when (K) over bar (n) is not the nonconvex (K) over bar (4), it can be 3-distinguished. Furthermore, when n >= 6, there is a (K) over bar (n) that can be 1-distinguished. For n >= 4, (K) over bar (2,n) can realize any distinguishing number between 1 and n inclusive. Finally, we show that every (K) over bar (3,3) can be 2-distinguished. We also offer several open questions. (C) 2006 Wiley Periodicals, Inc.