> information
Go back...The dual graph of a simple intersecting arrangement of $n \ge 3$ pseudocircles
has a unique embedding on the sphere
(cf. Section 8 in
Arrangements of Pseudocircles: On Circularizability).
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 exemplaric 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: July 09 2022 12:31:27.
(c) 2017 Stefan Felsner and Manfred Scheucher