Drawing Bobbin Lace Graphs, or, Fundamental Cycles for a Subclass of Periodic Graphs

Biedl, Therese and Irvine, Veronika (2017) Drawing Bobbin Lace Graphs, or, Fundamental Cycles for a Subclass of Periodic Graphs. In: Graph Drawing and Network Visualization, GD 2017, September 25-27 , pp. 140-152(Official URL: https://doi.org/10.1007/978-3-319-73915-1_12).

Full text not available from this repository.


In this paper, we study a class of graph drawings that arise from bobbin lace patterns. The drawings are periodic and require a combinatorial embedding with specific properties which we outline and demonstrate can be verified in linear time. In addition, a lace graph drawing has a topological requirement: it contains a set of non-contractible directed cycles which must be homotopic to (1, 0), that is, when drawn on a torus, each cycle wraps once around the minor meridian axis and zero times around the major longitude axis. We provide an algorithm for finding the two fundamental cycles of a canonical rectangular schema in a supergraph that enforces this topological constraint. The polygonal schema is then used to produce a straight-line drawing of the lace graph inside a rectangular frame. We argue that such a polygonal schema always exists for combinatorial embeddings satisfying the conditions of bobbin lace patterns, and that we can therefore create a pattern, given a graph with a fixed combinatorial embedding of genus one.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
P Styles > P.720 Straight-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1599

Actions (login required)

View Item View Item