> information

Go back...

The graph of an intersecting arrangement of pseudocircles is 3-connected and planar, hence, it has a unique dual TODO! To generate the intersecting arrangements we used the dual graphs and a procedure which produces the duals of all extensions by one additional pseudocircle of a given arrangement. The procedure is based on the observation that an extending pseudocircle for an arrangement of $n$ pseudocircles corresponds to a cycle of length $2n$ in the dual. A problem is that the same arrangement is usually generated many times. We used the canonical labeling provided by the Graph-package of SageMath to check whether an arrangement was found before. For readers, who want to get in touch with SageMath, the authors recommend the Sage Reference Manual on Graph Theory (available as PDF and HTML), which is well-documented and provides tons of excellent examples. We consider this dual graph representation of an arrangement as "model 1".

The graph of a connected arrangement may only be 2-connected. Since the graph is still plane, the dual is nevertheless well defined. To avoid problems with non-unique embeddings and multiple edges, we modelled connected arrangements with their primal-dual graphs where vertices, segments, and faces of the arrangement are represented by a vertex in the graph and two vertices share an edge if the corresponding entities are incident. We consider this primal-dual graph representation of an arrangement as "model 2".

Details on the encoding

We use following three plain-text formats for encoding graphs.

txt

In the txt-format, each line encodes the python-dictionary, whichs entries are pairs of vertices (a,b) that share an edge and the value is a color. The following dictionary encodes the dual graph of the "Krupp" arrangement of 3 pseudocircles:
 {(7, 3): 'green', (5, 4): 'blue', (6, 7): 'blue', (3, 0): 'red', (2, 1): 'red', (7, 4): 'red', (6, 2): 'green', (2, 3): 'blue', (5, 1): 'green', (1, 0): 'blue', (6, 5): 'red', (4, 0): 'green'}

mod1s6 and mod2s6

In the mod1s6 and mod2s6 format, each line encodes the sparse6 string of the dual graph and the primal-dual graph, respectively. The abreviation "modXs6" stands for "model X spase6". The following sparse6-string encodes the (uncolored) dual graph of the "Krupp" arrangement of 3 pseudocircles:
:GgXeBQAQAN
We remark that in SageMath one can simply run for example
sage: G = Graph(":GgXeBQAQAN")
sage: show(G)
to load and plot the dual graph of a Krupp arrangement. The following figure shows the resulting image.

Note that the sparse6 string does not decode the edge colors and, therefore, one needs to recompute the colors of an arrangement whenever needed. However, this can be done efficiently by propagating along the faces.

When encoding "model 2" graphs, we mark every vertex that correspond to a face of the arrangement by adding an auxiliary vertex and a pending edge. Note that auxiliary vertices are the only vertices of degree 1. The following sparse6-string encodes the (uncolored and marked) primal-dual graph of the "Krupp" arrangement of 3 pseudocircles:
:ae?`GmX?Baxs?GGgOOOadBBAYcWMIjP?gip@@`ZSCGDCO?O_VBA``SWMHDo?_[T@@?pN

Details on the visualization

On this website we provide a couple of figures which visualize certain arrangements of pseudocircles. These figures were automatically generated using iterative weighted Tutte embeddings of the primal graph (model 1) or of the primal-dual graphs (model 2). For more details we refer to Section 4 of our paper Arrangements of Pseudocircles: Triangles and Drawings. Our program is available on demand.

Go back...

Last update: November 16 2017 21:00:02. (c) 2017 Stefan Felsner and Manfred Scheucher