ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 317-336
Kronecker covers, V-construction, unit-distance graphs and isometric point-circle configurations*
Gâbor Gévay
Bolyai Institute, University of Szeged, Aradi vértanûk tere 1, H-6720 Szeged, Hungary
Tomaž Pisanski
Faculty of Mathematics and Physics, University of Ljubljana Jadranska 19, 1111 Ljubljana, Slovenia
Received 29 July 2012, accepted 17 March 2013, published online 1 June 2013
We call a convex polytope P of dimension 3 admissible if it has the following two properties: (1) for each vertex of P the set of its first-neighbours is coplanar; (2) all planes determined by the first-neighbours are distinct. It is shown that the Levi graph of a point-plane configuration obtained by V-construction from an admissible polytope P is the Kronecker cover of the 1-skeleton of P. We investigate the combinatorial nature of the V-construction and use it on unit-distance graphs to construct novel isometric point-circle configurations. In particular, we present an infinite series all of whose members are subconfigurations of the renowned Clifford configurations.
Keywords: V-construction, unit-distance graph, isometric point-circle configuration, Kronecker cover, Clifford configuration, Danzer configuration, generalized cuboctahedron graph. Math. Subj. Class.: 51A20, 52B10, 52C30, 05B30
1 Introduction
In this paper we investigate and carry over from polytopes to graphs the so-called V-construction, which was originally introduced in [16]. In this process we explain the construction in terms of the canonical double cover, also called the Kronecker cover of graphs. The reader is referred to [29] for graph coverings and to the monographs [22, 35] for the background on configurations and their Levi graphs.
*The authors acknowledge partial funding of this research via ARSS of Slovenia, grants: P1-0294 and N1-0011: GReGAS, supported in part by the European Science Foundation.
E-mail addresses: gevay@math.u-szeged.hu (Gabor Gévay), Tomaz.Pisanski@fmf.uni-lj.si (Tomaz Pisanski)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
340
Ars Math. Contemp. 7 (2014) 337-340
The first author used convex 3-polytopes in order to define a construction of geometric point-plane configurations in the following way [16].
Let P be a convex polytope of dimension 3 with the property that for each vertex v the set N(v) of its first neighbours (i.e., vertices adjacent to v) is coplanar. In particular, this will always be true if the graph (or 1-skeleton) of the polytope P is trivalent. There are several other classes of polytopes that have this property. Furthermore, we assume that all planes obtained in this way are distinct. In particular, this condition rules out bipyramids such as the octahedron. Let us call such a polytope admissible.
Proposition 1.1. Each convex 3-polytope with trivalent 1-skeleton is admissible.
Proof. Since each vertex of a 3-polytope with trivalent 1-skeleton has exactly three first-neighbours, they are clearly coplanar. An easy argument shows that if two trivalent vertices of a 3-polytope P share the same set of first-neighbours, then the 1-skeleton of P itself cannot be trivalent.	□
Suppose P is an admissible 3-polytope, and let V(P) denote the set of vertices of P and S(P) denote the set of planes passing through the first-neighbours of the vertices of P. Then the pair ((V(P),S(P)) defines a geometric incidence structure of points and planes with the usual incidence. We call this procedure the geometric V-construction. If the 1-skeleton of P is a k-valent graph, then each point of the configuration will sit on k planes (we remark that in this case, Euler's Theorem implies k = 3,4 or 5, see Section 10.1 in [20]). It immediately follows from the definition that each plane contains exactly k points. Let n be the number of vertices of P. Therefore, combinatorially, the incidence structure is an (nk ) configuration.
A natural question is what is the Levi graph of such a configuration. Recall that the Levi graph L(C) of a configuration C is a bipartite graph whose bipartition classes consist of the points and blocks of C, respectively, and two points in L(C) are adjacent if and only if the corresponding point and block in C are incident. Levi graphs are useful tools in studying configurations, because of the following property [9].
Lemma 1.2. A configuration C is uniquely determined by its Levi graph L(C).
Another, much more difficult, question is whether we can find any conditions under which such a combinatorial configuration may be realized geometrically as a configuration of points and lines. On the other hand, it may happen that a configuration can be realized in both a point-line version in the plane, and a point-plane version in space (cf. our example at the end of Section 2). In Section 3 and 5 we also present examples of configurations for which both point-line and point-circle realizations exist.
Point-circle configurations themselves are also interesting, since, in contrast to the point-line configurations, relatively little is known about them. The most notable achievement in this respect is undoubtedly Clifford's infinite series of configurations, going back to 1871 [10, 22]. In the last two sections we present a new construction of Clifford's configurations, as well as three new infinite series of point-circle configurations.
We note that the construction introduced in [16] is more general than needed here: instead of 3-dimensional polytopes one can take d-dimensional polytopes and accordingly, instead of planes one should consider hyperplanes. Also, instead of first-neighbours it is possible to consider second-neighbours. However, we do not consider these aspects of the V-construction here.
G. Gévay and T. Pisanski: Kronecker covers, V-construction,
319
2 Combinatorial V-construction
Let us generalize and carry out the V-construction on the abstract level.
To any regular graph G we may associate a combinatorial configuration. For a vertex v of G, denote by N(v) the set of vertices adjacent to v. Then take the family S(G) of these vertex-neighbourhoods:
S(G) = {N(v) | v G V(G)}.
The triple (V(G), S(G), g) defines a combinatorial incidence structure underlying the geometric configuration of points and planes for any 3-polytope P whose 1-skeleton is G. We shall denote this structure by N(G).
We note that a closely related construction occurs in the context of combinatorial geometries [31,40].
The following general result establishes a connection between Levi graphs and Kronecker covers. It will play a central role in our constructions presented in the rest of the paper. First, we recall that a graph G is said to be the Kronecker cover (or canonical double cover) of the graph G if there exists a 2:1 surjective homomorphism f : G ^ G such that for every vertex v of G the set of edges incident with v is mapped bijectively onto the set of edges incident with f (v) [29].
Theorem 2.1. Let G be a graph on n vertices and let L be the Levi graph of the incidence structure N(G). If no two vertices of G have the same neighbourhood, then L is the Kronecker cover of G.
Proof. Under the assumption that no two vertices have the same set of neighbours, all sets N(v), for v G V(G), are distinct. Therefore the set of vertices of L consists of V and
{N(v)|v G V(G)}. Each edge e = uv from G gives rise to two edges: uN(v) and vN(u). Hence L is a Kronecker cover of G. If |V(G)| = |{N(v)|v G V(G)}|, the argument fails.	□
Some direct consequences of Theorem 2.1 for Levi graphs are as follows.
Proposition 2.2. Let G be a graph on n vertices and let L be the Levi graph of the incidence structure N (G). The graph L is connected if and only if G is connected and non-bipartite.
Proof. If the graph G has no two vertices with a common neighborhood, the result follows from Theorem 2.1 and a well-known property of the Kronecker cover, see Proposition 1 of [29]. If this is not the case, the construction of L may be performed in two steps. First we construct the Kronecker cover H over G. We label the vertices of H in the following way. Let each vertex v of G give rise to two vertices v and v' of H in such a way that an edge uv of G gives rise to two edges uv' and u'v.
In the second step we identify any pair of vertices u' and v' of H if and only if N(u) = N(v) in G. The resulting graph is isomorphic to L. Such an identification may occur if and only if the vertices u in v are in the same bipartition set. This means that in the Kronecker cover only vertices in the same connected component may be identified and the result follows.	□
Proposition 2.3. Let G be a k-valent graph on n vertices and let L be the Levi graph of the incidence structure N(G). Then N(G) is a combinatorial (nk) point-line configuration if and only if L contains no cycle of length 4.
340
Ars Math. Contemp. 7 (2014) 337-340
Proof. In the Kronecker cover odd cycles of length r lift to cycles of length 2r, while even cycles lift to two cycles of the same length. Hence the girth of the Kronecker cover is 4 if and only if the original graph contains a 4-cycle. Since Kronecker cover is bipartite, the alternative means girth at least 6.	□
By analogy with geometric V-construction, we call a graph G admissible if no two of its vertices have a common neighborhood. Recall that a configuration is combinatorially self-polar if there exists an automorphism of order two of its Levi graph interchanging the two parts of bipartition; see for instance [35].
Theorem 2.4. A configuration that is obtained by V-construction from an admissible graph G is combinatorially self-polar.
Proof. By our previous discussion the Levi graph of this configuration is a Kronecker cover over G. The involution that switches at the same time the vertices in each fiber is a self-polarity. This follows from the fact that any double cover is a regular cover.	□
We shall use the following result, which is an easy consequence of Proposition 1 in [29] and our Theorem 2.1.
Proposition 2.5. Let C be a configuration obtained from an admissible graph G by V-construction. Then the Levi graph L(C) is bipartite. If G is bipartite, then L(C) consists of two disjoint copies of G.
Corollary 2.6. Applying the V-construction to the Levi graph of configuration C from Proposition 2.5 results in a configuration C which consists of two disjoint copies of C.
We conclude this section with the following example. Let G be the dodecahedron graph. Then N(G) is a configuration (203). If G is embedded in E3 as the 1-skeleton of the regular dodecahedron, then N(G) is realized as a geometric point-plane configuration (see Figure 1).
We note that the same configuration is obtained by taking the 20 vertices and the planes spanned by the 20 triangular faces of either the small ditrigonal icosidodecahedron or the great ditrigonal icosidodecahedron (these polyhedra belong to the class of the 53 non-regular non-convex uniform polyhedra [11, 25]).
On the other hand, we know that the Kronecker cover of the dodecahedron graph is isomorphic to the Levi graph of the unique triangle-free, flag-transitive (203) point-line configuration [5] (Figure 2) (see also Figure 1 in [4]). Thus we see that N(G) can be realized geometrically as both a point-plane and a point-line configuration. As we show in the next section, a realization as a point-circle configuration may also be of interest.
3 V-construction and configurations of points and circles
In [16] it was observed that certain point-plane configurations obtained from a 3-polytope P by the V-construction could also be realized by points and circles. A simple necessary condition for this is that for each vertex v of P, the set of the first-neighbours of v forms a concyclic set, i.e. one can draw a circle through its points. Moreover, such point-circle configurations can be carried over to the plane, using stereographic projection. Here the well-known property is used that the stereographic projection is a circle-preserving map, see for instance [26] (also [10, 24]).
G. Gévay and T. Pisanski: Kronecker covers, V-construction,
321
Figure 1: The (203) point-plane configuration obtained from the regular dodecahedron by the V-construction. Each plane is indicated by the convex hull of the three vertices spanning it.
J	3
9	9
(a)	(b)
Figure 2: The flag-transitive triangle-free point-line configuration (203) (a), and its Levi graph (b).
322
Ars Math. Contemp. 7(2014) 317-336
Lemma 3.1. Under stereographic projection from the sphere S to the plane £ the image of any circle on S is a circle on £.
A straightforward application of this leads to the following result.
Theorem 3.2. Any point-circle configuration on the sphere gives rise to a planar point-circle configuration.
Here we explicitly state the result that is presented already in [16] (see Table 1 and 2 there), and follows readily from Theorem 3.2.
Corollary 3.3. The V-construction on any Platonic or Archimedean polyhedron except for the octahedron gives rise to a planar point-circle configuration.
An example obtained from the regular dodecahedron is depicted in Figure 3. (Note that together with this, we have three distinct geometric realizations of the same combinatorial configuration of type (203); cf. Figures 1 and 2.)
Figure 3: (203) point-circle configuration obtained from the regular dodecahedron by V-construction.
We remark that applying highly symmetric polytopes as a "scaffolding" for the construction of spatial point-line configurations is extensively used in [17].
The V-construction on 3-polytopes may also work in more generality. We recall the following theorem, which is a consequence of the Koebe-Andreev-Thurston circle-packing theorem (for further details, and some related problems, see [20, 37, 38, 42]).
Theorem 3.4. Every convex 3-polytope P can be realized with all edges tangent to a sphere S ; that is, there exists a combinatorially equivalent copy Q of P with all its edges tangent to S.
G. Gévay and T. Pisanski: Kronecker covers, V-construction,
323
This leads to the following conjecture that was essentially suggested by one of the referees.
Conjecture 3.5. Let P be any convex 3-polytope other than a bipyramid such that its 1-skeleton is a regular graph. Then the combinatorial configuration obtained by V-construc-tionfrom the graph of P can be realized as a point-circle configuration on the 2-sphere, and hence, in plane.
In fact, the edges emanating from a vertex v of P touch the sphere S in points lying on a circle in S, and these points of contact are basically the same (combinatorially speaking) as the vertices of P adjacent to v. Of course, the circles will not meet in vertices of P. Still, it might be worth seeing if the conjecture is true.
In what follows we consider some other cases of V-construction that also give rise to planar point-circle configurations.
Proposition 3.6. Any (n3) configuration can be realized by points and circles in the plane.
Proof. We may place the n points in the plane in general position, in such a way that no three lie on a line and no four lie on a circle. Obviously combinatorial lines can be realized by circles, and the combinatorial incidence is carried over to a geometric point-circle incidence.	□
The (n3) point-circle configurations have an important property that is not shared by all point-circle configurations; namely, they are movable. To see this notion, we should consider that in the simplest case the point-circle configurations are constructed in the Euclidean plane E2. However, by adding to E2 a single point at infinity, we may as well consider them as lying in the inversive plane [10]. Under this consideration, we say that a point-circle configuration is rigid if its geometric realizations form a single class under circle-preserving transformations of the inversive plane.
We note that point-circle configurations can also be considered on the extended complex plane; in this case the circle-preserving transformations are just the Mobius transformations, i.e. fractional linear transformations [24]. Incidentally, these latter play an important role in the so-called Lombardi drawings of graphs, an idea not totally unrelated to point-circle configurations and studied by D. Eppstein and his co-authors, for instance in [12].
Having defined rigidity above, we say that a point-line configuration is movable if is not rigid (cf. the notion of movability of point-line configurations, as defined in [22]). The following statement is a straightforward consequence of this definiton.
Proposition 3.7. Any (n3) point-circle configuration is movable.
We note that movability is not a general property even for point-line configurations; for example, some classes of movable (n4) configurations were discovered just recently [2, 3].
There is another property that distinguishes (n3) point-circle configurations among all configurations. In general, the circles may be of different size. Let r be the number of radii used in this construction. If r = 1, all circles are of the same size, and the configuration is called an isometric point-circle configuration. It is not clear which (n3) configurations can be realized as planar isometric point-circle configurations.
There is a large class of graphs that yields by V-construction isometric point-circle configurations in a natural way. These are the unit-distance graphs, i.e. graphs all of whose edges have the same length (cf. [27, 28, 43]).
340
Ars Math. Contemp. 7 (2014) 337-340
Theorem 3.8. Let G be a regular d-valent graph that is a unit-distance graph on n vertices in the plane. Then N(G) is an (nd) configuration, realizable as an isometric point-circle configuration.
Proof. The points of the configuration are the vertices of the graph, as drawn in the plane. The unit-distance property implies that for each vertex, the set of its first-neighbours forms a concyclic set; furthermore, all these circles are of the same size.	□
Figure 4: Applying the V-construction to a unit-distance representation of the Petersen graph (a) yields an isometric point-circle realization of Desargues' configuration (b).
An interesting example is as follows. We know unit-distance representations of the Petersen graph [28, 43]; on the other hand, it is well known that the Kronecker cover of the Petersen graph is the Desargues graph [29] (which, in turn, is the Levi graph of the Desargues configuration [9]). Thus, by Theorem 2.1, the V-construction on a unit-distance representation of the Petersen graph yields an isometric point-circle realization of the Desargues configuration (see Figure 4).
We remark that the Desargues graph also has a unit-distance representation [43]. Thus one may also apply to it the V-construction, so as to obtain an isometric point-circle configuration. By our Corollary 2.6, this (203) configuration decomposes into two disjoint copies of the (103) Desargues point-circle configuration (see Figure 5, where the construction yields the two (103 ) copies in centrally symmetric position with respect to their common centre).
We mention an additional property which a point-circle configuration may or may not possess. We call a point-circle configuration C lineal if two circles meet in at most one point of C. This property depends on the combinatorial structure of C; in other words, C is lineal if and only if the underlying combinatorial configuration possesses an analogous property. In simple cases, lineality can be decided quite easily; even visual observation may suffice (provided a graphical representation is available). For example, the (203) configuration in Figure 3 is lineal. Clearly, so is any point-circle representation of the Desargues configuration. On the other hand, examples of Clifford's point-circle configurations, shown
G. Gévay and T. Pisanski: Kronecker covers, V-construction,
325
Figure 5: Applying the V-construction to a unit-distance representation of the Desargues graph (a) yields a configuration consisting of two disjoint copies of another isometric realization of the point-circle Desargues configuration (b). One of the two copies can be viewed in Figure 8.
in Figures 6 and 7 in the next section, are not lineal. Here we give a criterion that can be used in some cases, like e.g. the whole series of the Clifford configurations.
Proposition 3.9. A point-circle configuration C is lineal if and only if its Levi graph L(C) contains no cycle of length 4. In particular, suppose C can obtained by V-construction from a graph G. Then C is lineal if and only if G contains no cycle of length 4.
Proof. Observe that a cycle of length 4 in L(C) is a complete bipartite graph K2,2 such that one pair of its non-adjacent vertices corresponds to a pair of points (P1 ,P2) in C, and the other pair of its non-adjacent vertices corresponds to a pair of circles meeting in (P1, P2). Hence the proof goes along the same lines as that of Proposition 2.3.	□
4 V-construction on d-cubes and Clifford's point-circle configurations
The particular case of the cube in Corollary 3.3 can be extended to the whole class of d-cubes. Because of its interesting connections, we discuss here the general case in some detail.
We recall the infinite series of Clifford's point-circle configurations, which is associated to his renowned chain of theorems. By Coxeter [10], these theorems can be formulated as follows.
Theorem 4.1 (Clifford's chain of theorems).
(1)	Let a1, a2, a3, a4 be four circles of general position through a point S. Let Sij be the second intersection of the circles ai and Oj. Let aijk denote the circle Sij Sik Sjk. Then the four circles a234, 0134, o124, o123 all pass through one point S1234.
(2)	Let 05 be a fifth circle through S. Then the five points S2345, S1345, S1245, S1235, S1234 all lie on one circle a12345.
340
Ars Math. Contemp. 7 (2014) 337-340
(3) The six circles ^23455, ^13456, ^12456, ^12356, ^12346, ^12345 all pass through one point S123456. And so on.
We note that these circles can be considered as lying either in the (inversive) plane or on the 2-sphere. We know the Levi graph of these configurations (Coxeter [9, 10]).
Lemma 4.2. The Levi graph of the Clifford configuration of type (2^-1 ) is isomorphic to the d-cube graph.
It turns out that our V-construction can be applied so as to obtain Clifford's configurations.
Theorem 4.3. The V-construction on a d-cube graph gives rise to an isometric (2^) point-circle configuration in the plane. This configuration is disconnected and composed of two copies of isometric (2^-1 ) point-circle configurations which are isomorphic to a member of the same type of Clifford's infinite series of configurations.
Proof. The d-cube graph is the Cartesian product of d edge graphs K2. According to [27], it is a unit-distance graph. By Theorem 3.8, the V-construction applied on it gives rise to an isometric point-circle configuration C. Since the d-cube graph is bipartite, its Kronecker cover is composed of two disjoint isomorphic copies of the d-cube graph (by Proposition 1 in [29]). By Theorem 2.1, this Kronecker cover is the Levi graph of C. Since a configuration is uniquely determined by its Levi graph (by Lemma 1.2), it follows from Lemma 4.2 that C is in fact composed of two disjoint copies of Clifford configurations of type (2d-1 ).	□
Some smallest examples are depicted in Figures 6 and 7.
Figure 6: Isometric realization of Clifford configurations: (43) derived from the 3-cube graph (a), and (84) derived from the 4-cube graph (b).
It is easy to see that the d-cube graph can be realized in the plane as a unit-distance graph in continuum many ways. In fact, take an arbitrary vertex and place it in the center of a unit circle. Its first-neighbours can be placed in different positions on the circle. Positions
G. Gévay and T. Pisanski: Kronecker covers, V-construction,
327
Figure 7: Isometric realization of Clifford's configuration (165) derived from the 5-cube graph.
of the remaining vertices are then uniquely determined by sequences of rhombuses. This immediately gives the following corollary.
Corollary 4.4. Every Clifford configuration is realizable as a movable isometric point-circle configuration.
Remark 4.5. Realizability of Clifford's configurations with circles of equal size is already known from [41] (see also [1]). Our approach provides an independent proof of this result.
5 Three new infinite classes of point-circle configurations
We start from the following observation. When applying the V-construction so as to obtain an isometric point-circle realization of Desargues' configuration, the underlying Petersen graph need not be represented in unit-distance form. Indeed, compare our Figures 4 and 8. (We remark that the version depicted in Figure 8b is precisely the same as one of the components of the (203) configuration in Figure 5b.)
Now Figure 8b suggests that this latter realization can be extended to a Clifford configuration of type (165 ). Figure 9 shows that such an extension is in fact possible (see also Figure 7). It turns out that this is a particular case of a more general relationship.
Before formulating it, recall that the Kneser graph K(n, k) has as vertices the k-subsets of an n-element set, where two vertices are adjacent if the k-subsets are disjoint [19]. The Kneser graph K(2n — 1, n — 1) is called an odd graph and is denoted by On. In particular, O3 = K(5, 2) is isomorphic to the Petersen graph. The bipartite Kneser graph H (n, k) has as its bipartition sets the k- and (n — k)-subsets of an n-element set, respectively, and the adjacency is given by containment. Although the following relationship is well-known, we give a short proof of it.
Lemma 5.1. The bipartite Kneser graph H(n, k) is the Kronecker cover of the Kneser graph K(n,k).
328
ArsMath. Contemp. 7(2014) 317-336
(a)	(b)
Figure 8: Isometric point-circle realization of Desargues' configuration arising from a non-unit-distance representation of the Petersen graph. (Note that this is a degenerate representation in the sense that there are edges overlapping along the sides of the inner pentagon.)
Figure 9: The Desargues point-circle configuration extended to the Clifford configuration (165 ).
Proof. Let A and B be two k-subsets and let A/ and B/ be their respective (n — k)-complements. Clearly A is adjacent to B in K(n, k) if and only if A is adjacent to B/ and B is adjacent to A/ in H (n, k ), and the result follows readily.	□
The bipartite Kneser graph H(2n — 1,n — 1) is also known as the revolving door graph, or middle-levels graph; the latter name comes from the fact that it is a special
G. Gévay and T. Pisanski: Kronecker covers, V-construction,
329
subgraph of the (2n — 1)-cube graph Q2n-1 (considering Q2n-1 as the Hasse diagram of the corresponding Boolean lattice) [36, 39]. It is a regular graph with degree n. Note that middle-levels graph is called a medial layer graph in [33] and is defined for any abstract polytope of odd rank.
Theorem 5.2. For all n > 3, there exists an isometric point-circle configuration of type
2 n — 1 n1
It is a subconfiguration of the Clifford configuration of type (2^-1) • It can be obtained from the odd graph On by V-construction.
Proof. Let C be an incidence structure obtained from the odd graph On by V-construction. By Theorem 2.1, the Levi graph of C is the Kronecker cover of On. Lemma 5.1 implies that it is the bipartite Kneser graph H (2n — 1,n — 1). Since this graph is a subgraph of the (2n — 1)-cube graph Q2n-1, from Lemma 1.2 follows that C is isomorphic to a subconfiguration of the Clifford configuration of type (2^-1). Hence it can be realized as a planar point-circle configuration. The type of this configuration follows from the definition of On. Furthermore, Corollary 4.4 implies that this configuration also has an isometric realization.	□
Figure 10: A point-circle realization of Danzer's (354) configuration.
340
Ars Math. Contemp. 7 (2014) 337-340
Remark 5.3. Proposition 3.9 and Lemma 4.2 together imply that the Clifford configurations are not lineal. In contrast to this, it can be proved that their subconfigurations given by Theorem 5.2 are lineal. We leave the details to a subsequent paper.
In the particular case of n = 4 we have (354), which provides a point-circle realization of Danzer's combinatorial (354) configuration (see Figure 10 for a non-isometric version). On this latter, Griinbaum wrote in 2008 [21]: "It seems that any representation of Danzer's configuration is of necessity so cluttered and unhelpful for visualization that no attempt to present it has ever been made." (see also [23]).
We emphasize the geometric symmetry of this realization, which is the highest possible in the planar case; namely, D7.
Our next new class also consists of isometric point-circle configurations.
Theorem 5.4. For any N and any d > 2 there exists an isometric (nd) point-circle configuration with n > N.
Proof. Take the Cartesian product of a long odd cycle CN and a (d - 2)-dimensional cube graph. This is a unit-distance graph. Apply the V-construction to it.	□
Finally, we construct an infinite series of non-isometric (n4 ) point-circle configurations. We start from a prism P over an n-gon (n > 3) (the corresponding graph is also called a circular ladder). Then we take its medial Me(P) [19, 34, 14], i.e. a new polyhedron such that its vertices are the midpoints of the original edges, and for each original vertex, the midpoints of the edges emanating from it are connected by new edges, forming a 3-cycle. In terms of solid geometry, the medial corresponds to a truncation of a right n-sided prism such that each truncating plane at a vertex is spanned by the midpoints of the edges incident with the given vertex ("deep vertex truncation", see [42]). Note that in the particular case when the prism is the cube, its medial is the Archimedean solid called a cuboctahedron. Accordingly, we define the generalized cuboctahedron graph as the 1-skeleton of Me(P), and denote it by CO(n). Note that this graph can equivalently be defined as the line graph of the prism graph.
Observe that CO(n) is a 4-valent regular graph with 3n vertices. Moreover, it has a representation in the plane such that it exhibits the symmetry of a regular n-gon (thus its symmetry group is Dn); in this case its vertices lie on three concentric circles, n vertices on each. It follows that the first-neighbour sets of the vertices are concyclic, hence the V-construction can be applied. Thus we obtain the following result.
Theorem 5.5. For any n > 3, there exists a ((3n)4) point-circle configuration obtained from the generalized cuboctahedron graph CO(n) by V-construction. It can be realized in the plane so that its symmetry group is the dihedral group Dn.
An example with n = 7 is depicted in Figure 11. It is an open question if any member of the infinite series of these ((3n)4) configurations has an isometric realization.
On the other hand, the mutual position of the points on the three orbits makes it possible to arrange the circles in several different ways, so as to obtain new, pairwise non-isomorphic ((3n)4) configurations. Here we do not investigate this possibility in detail. Instead, we just present an example, also of type (214) (non-isomorphic with the previous one), whose original point-line version is remarkable for several reasons (see Figure 12). We only mention here that it goes back to Felix Klein, 1879 (for further details, see [23]); on the other hand, its first graphic depiction only appeared in 1990 [21, 23]. This configuration also
G. Gévay and T. Pisanski: Kronecker covers, V-construction,
331
Figure 11: A representation of the generalized cuboctahedron graph with D7 symmetry (a), and a (214) point-circle configuration obtained from it by V-construction (b).
(a)	(b)
Figure 12: The point-line (214) configuration of Griinbaum and Rigby (a), and one of its point-circle realizations with dihedral symmetry (b).
motivated the authors of [32] to present some geometric representations of a certain family of configurations that became later known as polycyclic configurations [6].
We note that several other already known families of graphs can serve as a basis for obtaining new point-circle configurations by V-construction; just to mention some of them: generalized Petersen graphs [34], I-graphs [7]. In addition, the 1-skeleton of equivelar polyhedra is also a regular graph (see e.g. [18]); hence, finding suitable planar representa-
340
Ars Math. Contemp. 7 (2014) 337-340
tions among them may also be promising in this respect.
6 Some comparisons beween different realizations of configurations
Comparing point-line and point-circle configurations, several questions arise, in particular, when different kinds of geometric realization of the same combinatorial configuration is considered. First we make the following conceptual distinction. Clearly, every point-line configuration can be transformed into a point-circle configuration by some suitable inversion. However, in this case, all the circles will have a common point (the inverse image of the point at infinity). To rule out this case, we use the term improper point-circle configuration. Accordingly, we call a point-circle configuration proper if its circles are not all incident with a common point. Clearly, all our examples presented in the previous sections are proper point-circle configurations. In what follows, we shall also speak about such configurations, and mostly omit the attribute "proper".
A simple consequence of Proposition 3.6 is that by suitable displacement of the points, any planar (n3 ) point-line configuration can transformed into a point-circle configuration. For an incidence number larger than 3, it is more difficult to decide the existence of a point-circle representation of a point-line configuration.
Problem 6.1. For k > 4, find an (nk ) point-line configuration which cannot be represented by a proper point-circle configuration.
The converse problem, in general, can also be quite difficult. However, here we know several examples. One of the oldest one is Miquel's (83,64) (for a simple proof why it has no point-line representation, see [35]). The infinite series of Clifford configurations also provides quite old (balanced) examples. In fact, since all the higher members contain, as a subconfiguration, the initial member of type (43 ), they cannot be represented by point-line configurations.
In the particular case of incidence number k = 4, we have the following lower bound (a result of Bokowski and Schewe [8]).
Theorem 6.2. For n < 17, there are no geometric point-line configurations (n4).
As a consequence, consider e.g. the generalized Petersen graph GP(n,r) [34]. For n < 8 it yields, by V-construction, a point-circle configuration which has no point-line representation.
In Section 3 we introduced the notion of an isometric point-circle configuration. We also distinguished point-circle configurations according as they are lineal or not. We may impose a further condition, which, together with the former two, determines a particularly nice class of configurations. We call a point-circle configuration C determining if the set of points of C coincides with the set of points in which more than two circles of C meet.
Note that while the first two conditions determine a property on more abstract level, the latter may depend on a particular representation of C. For example, Figure 4b shows a determining representation of the Desargues configuration, while that in Figure 8b is non-determining.
Now we call C perfect if it is lineal, isometric and determining. For example, the Desargues configuration in Figure 4b is perfect.
Problem 6.3. Which configurations of points and lines can be realized as perfect point-circle configurations?
G. Gévay and T. Pisanski: Kronecker covers, V-construction,
333
Geometric symmetry is also an interesting property which is worth investigating when different realizations of the same combinatorial configuration are compared. Are all symmetries of a point-line configuration realizable in its representation by points and circles? Of course, the converse question can also arise. Here we only mention that e.g. for the Pappus configuration not only its realization by lines can exhibit the maximal possible symmetry (D3), but it can also be realized by circles with the same symmetry (see Figure 13).
On the other hand, it is a remarkable fact that while the Desargues configuration can be represented by points and lines with symmetry group either C5 or D5 (see Figures 4b and 8b, respectively), its classical point-line version can exist with neither of these symmetries. This follows from the theory developed in the paper [7] on I-graphs and the corresponding configurations. (We note that geometric realization of certain combinatorial objects with maximal symmetry is, in general, a problem which is far from trivial, see e.g. [15], and the references therein.)
(a)	(b)
Figure 13: Two different realizations of Pappus' configuration with symmetry D3.
Considering point-circle realizations of the two oldest configurations, yet another difference occurs. Note that while Desargues' configuration has a perfect realization (shown by Figure 4b), the realization of Pappus' configuration shown by Figure 13b is not isometric (thus it is not perfect). On the other hand, when constructing an isometric representation, we find that it is no longer a determining representation (see the central triple crossing point in Figure 14b). This version is obtained from a unit-distance representation of the Pappus graph (see Figure 14a), using Corollary 2.6. Note that the symmetry reduces here to C3 (for a representation of the Pappus graph with D3 symmetry, see e.g. [34], Figure 21).
Acknowledgements
The authors would like to thank Marko Boben for careful reading of the manuscript, for pointing out that some circles in the (214) configuration on Figure 11(b) meet in two points, which is an easy proof that the configuration is not isomorphic to Klein's (214) configuration from [23], and for checking that Danzer's combinatorial (354 ) configuration actually admits a geometric realization and is hidden in the renowned Pascal's Hexagrammum mys-
334
ArsMath. Contemp. 7(2014) 317-336
Figure 14: Unit-distance representation of the Pappus graph (a), and isometric point-circle
representation of the Pappus configuration derived from it (b).
ticum [30]. Last but not least we would like to thank the anonymous referee for encouraging
us to pose Conjecture 3.5.
References
[1]	D. W. Babbage, A chain of theorems for circles, Bull. London Math. Soc. 1 (1969), 343-344.
[2]	L. W. Berman, Movable (n) configurations, Electron. J. Combin. 13 (2006), #R104.
[3]	L. W. Berman, J. Bokowski, B. Griinbaum and T. Pisanski, Geometric "floral" configurations, Can. Math. Bull. 52 (2009), 327-341.
[4]	A. Betten, G. Brinkmann and T. Pisanski, Counting symmetric v3 configurations, Discrete Applied Math. 99 (2000), 331-338.
[5]	M. Boben, B. Grimbaum, T. Pisanski and A. Zitnik, Small triangle-free configurations of points and lines, Discrete Comput. Geom. 35 (2006), 405-427.
[6]	M. Boben and T. Pisanski, Polycyclic configurations, European J. Combin. 24 (2003), 431457.
[7]	M. Boben, T. Pisanski and A. Zitnik, I-graphs and the corresponding configurations, J. Comb. Des. 13 (2005) 406-424.
[8]	J. Bokowski and L. Schewe, On the finite set of missing geometric configurations (n4 ), Comput. Geom. 46 (2013) 532-540.
[9]	H. S. M. Coxeter, Self-dual configurations and regular graphs, Bull. Amer. Math. Soc. 56 (1950), 413-455. Reprinted in: H. S. M. Coxeter, Twelve Geometric Essays, Southern Illinois University Press, Carbondale, 1968, 106-149.
[10]	H. S. M. Coxeter, Introduction to Geometry, Wiley, New York, 1961.
[11]	H. S. M. Coxeter, M. S. Longuet-Higgins and J. C. P. Miller, Uniform polyhedra, Phil. Trans. Roy. Soc. London Ser. A 246 (1954), 401-450.
[12]	C. A. Duncan, D. Eppstein, M. T. Goodrich, S. G. Kobourov and M. Nollenburg, Lombardi drawings of graphs, J. Graph Algorithms Appl. 16 (2012), 37-83.
G. Gévay and T. Pisanski: Kronecker covers, V-construction,
335
[13]	P. Erdos, F. Harary and W. T. Tutte, On the dimension of a graph, Mathematika 12 (1965), 118-122.
[14]	P. Fowler and T. Pisanski, Leapfrog transformations and polyhedra of Clar type, J. Chem. Soc. Faraday Trans. 90 (1994), 2865-2871.
[15]	G. Gevay, A class of cellulated spheres with non-polytopal symmetries, Canad. Math. Bull. 52 (2009), 366-379.
[16]	G. Gevay, Symmetric configurations and the different levels of their symmetry, Symmetry Cult. Sci. 20 (2009), 309-329.
[17]	G. Gevay, Constructions for large spatial point-line (nk) configurations, Ars Math. Contemp. 7 (2014) 175-199.
[18]	G. Gevay and J. M. Wills, On regular and equivelar Leonardo polyhedra, Ars Math. Contemp. 6 (2013), 1-11.
[19]	C. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001.
[20]	B. Grunbaum, Convex Polytopes, Graduate Texts in Mathematics, Vol. 221, Springer-Verlag, New York, 2003. (Second edition prepared by V. Kaibel, V. Klee and G. M. Ziegler).
[21]	B. Grunbaum, Musings on an example of Danzer's, European J. Combin. 29 (2008), 19101918.
[22]	B. Grunbaum, Configurations of Points and Lines, Graduate Texts in Mathematics, Vol. 103, American Mathematical Society, Providence, Rhode Island, 2009.
[23]	B. Grunbaum and J. F. Rigby, The real configuration (2I4), J. London Math. Soc. 41 (1990), 336-346.
[24]	L. Hahn, Complex Numbers and Geometry, The Mathematical Association of America, Washington, D. C. 1994.
[25]	Z. Har'El, Uniform solution for uniform polyhedra, Geom. Dedicata 47 (1993), 57-110.
[26]	D. Hilbert and S. Cohn-Vossen, Geometry and Imagination, Chelsea Publishing Company, NY 1952.
[27]	B. Horvat and T. Pisanski, Products of unit distance graphs, Discrete Math. 310 (2010), 17831792.
[28]	B. Horvat and T. Pisanski, Unit-distance representations of the Petersen graph in the plane, Ars Combin. 104 (2012), 393-415.
[29]	W. Imrich and T. Pisanski, Multiple Kronecker covering graphs, European J. Combin. 29 (2008), 1116-1122.
[30]	L. Klug, Az ältalänos es negy különös Pascal-hatszog configuratioja (The Configuration of the General and Four Special Pascal Hexagons; in Hungarian), Ajtai K. Albert Konyvnyomdaja, Kolozsvar, 1898. Reprinted in: L. Klug, Die Configuration Des Pascal'schen Sechseckes Im Allgemeinen Und in Vier Speciellen Fällen (German Edition), Nabu Press, 2010.
[31]	C. Lefevre-Percsy, N. Percsy and D. Leemans, New geometries for finite groups and polytopes, Bull. Belg. Math. Soc. Simon Stevin 7 (2000), 583-610.
[32]	D. Marusic and T. Pisanski, Weakly flag-transitive configurations and half-arc-transitive graphs, European J. Combin. 20 (1999), 559-570.
[33]	B. Monson, T. Pisanski, E. Schulte and A. Ivic Weiss, Semisymmetric graphs from polytopes, J. Combin. Theory A 114 (2007), 421-435.
[34]	T. Pisanski and M. Randic, Bridges between geometry and graph theory, in C. A. Gorini (ed.), Geometry at Work, MAA Notes 53, Math. Assoc. America, Washington, DC, 2000, pp. 174194.
340
Ars Math. Contemp. 7 (2014) 337-340
[35]	T. Pisanski and B. Servatius, Configurations from a Graphical Viewpoint, Birkhäuser Advanced Texts Basler Lehrbücher Series, Birkhauser Boston Inc., Boston, 2012.
[36]	J. J. Quinn and A. T. Benjamin, Strong chromatic index of subset graphs, J. Graph Theory 24 (1997), 267-273.
[37]	O. Schramm, How to cage an egg, Invent. Math. 107 (1992), 543-560.
[38]	E. Schulte, Analogues of Steinitz's theorem about non-inscribable polytopes, in: K. Boroczky and G. Fejes Toth (eds.), Intuitive Geometry. Siofok, 1985 Colloq. Math. Soc. Janos Bolyai, Vol. 48, North-Holland - Math. Soc. Janos Bolyai, Budapest, 1987, pp. 503-516.
[39]	I. Shields, B. J. Shields and C. D. Savage, An update on the middle levels problem, Discrete Math. 309 (2009), 5271-5277.
[40]	H. Van Maldeghem, Slim and bislim geometries, in: A. Pasini (ed.) Topics in Diagram Geometry, Quaderni di Matematiche 12, Aracne, Roma, 2003, pp. 227-254.
[41]	P. Ziegenbein, Konfigurationen in der Kreisgeometrie, J. Reine Angew. Math. 183 (1940), 9-24.
[42]	G. M. Ziegler, Convex polytopes: extremal constructions and f -vector shapes, in: E. Miller, V. Reiner and B. Sturmfels (eds.), Geometric Combinatorics, IAS/Park City Math. Ser. Vol. 13, American Mathematical Society - Institute for Advanced Study, 2007, pp. 617-691.
[43]	A. Zitnik, B. Horvat and T. Pisanski, All generalized Petersen graphs are unit-distance graphs J. Korean Math. Soc. 49 (2012), 475-491.